#P15080. [2026省选联测]小清新序列

    ID: 14296 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000数论模运算中国剩余定理枚举树状数组模拟排序

[2026省选联测]小清新序列

题意

给定 n,a,b,c,dn,a,b,c,d。

有长度为 nn 的序列 A,BA,B 满足 Ai=ai mod c,Bi=bi mod dA_{i}=a^i\bmod c,B_{i}=b^i\bmod d。

求:∑i=1n[Ai=Bi]\sum_{i=1}^n[A_i=B_i]。

输入格式

第一行输入一个整数 TT,代表数据组数。

对于每组数据:一行五个正整数,依次为 n,a,b,c,dn,a,b,c,d,含义如题面所述。

输出格式

输出 TT 行,每行一个整数,表示每组数据的答案。

样例 #1

样例输入 #1

2
10 2 3 7 11
20 2 3 7 11

样例输出 #1

0
2

数据范围与提示

子任务编号 n≤n\leq a,b≤a,b\leq c,d≤c,d\leq 特殊性质 子任务分值
11 101810^{18} 11 10710^7 无 11
22 10710^7 101810^{18} 1515
33 101810^{18} AA 2424
44 BB 3030
55 无

特殊性质 A:A: lcm(c−1,d−1)≤107\mathrm{lcm}(c-1,d-1)\leq10^7。

特殊性质 B:B: n mod lcm(c−1,d−1)=0n\bmod\mathrm{lcm}(c-1,d-1)=0。

对于所有数据,满足 $1 \leq T \leq5,1\leq n,a,b \leq 10^{18},1\leq c,d \leq 10^7$。

保证 c,dc,d 均为质数。