数论大杂烩。

\[ x^A\equiv B \pmod C \] 考虑 \(CRT\) , 把模数拆分成质数的次幂的形式,把每个同余方程的解数量相乘即是答案。

一般模数不为质数就可能要 \(CRT\) 。然后只需求 \[ x^A \equiv B \pmod {p^a} \] 现在考虑 \(x^A\), 可以用原根,两边取指标做。

但指标存在需要 \(gcd(B,p^a)=1\) , 所以考虑除去 \(gcd\) : \[ x^A \equiv B'p^d \pmod{p^a} \\ \] 特判 \(d \ge a\) 的情况。

\[ (\frac{x}{p^{\frac d A}})^A \equiv B' \pmod{p^{a-d}} \] 注意到一定有 \(A|d\) ,否则无解。

然后

\[ y^A\equiv B' \pmod{ p^{a-d}} \\ A\text{ ind }y\equiv \text{ ind } B' \pmod{\varphi(p^{a-d}) } \\ Az \equiv D \pmod{ m } \]

这就是个 \(exgcd\) ,容易得到 \(z\) 的解数应是 \(gcd(A,m)\)

这是因为 \(ax+by=gcd(a,b)\)\(x\)\([0,b-1]\) 范围解数是 \(gcd(a,b)\) 。挺显然的。

注意 \(x\) 解的个数应是 \(z\) 的个数的 \(p^{d-\frac d A}\) 倍。

所以我们要求原根,\(BSGS\)\(ind\) ,还用到 \(CRT\) 的思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<cstdio>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100005;
typedef long long LL;
int Count(int p,int &x){
int res=0;
while(x%p==0) x/=p, res++;
return res;
}
int Pow(LL a,LL b,int P=2e9){
LL res=1;
for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;
return res;
}
int getG(int p){
int x=p-1;
for(int g=2,pd;;g++){
pd=1;
for(int i=2;i*i<=x&&pd;i++)
if(x%i==0){
if(Pow(g,(p-1)/i,p)==1) pd=0;
if(Pow(g,i,p)==1) pd=0;
}
if(pd) return g;
}
}
map<int,int> M;
int getInd(int A,int p,int a){
int g=getG(p), P=Pow(p,a), phi_P=Pow(p,a-1)*(p-1); //printf("G=%d\n",g);
int m=sqrt(phi_P)+2; M.clear();
int inv_g=Pow(g,phi_P-1,P);
for(int i=0,now=1;i<=m-1;i++,now=(LL)now*inv_g%P) M[(LL)A*now%P]=i;
int g_m=Pow(g,m,P);
for(int i=0,now=1;i<=m;i++,now=(LL)now*g_m%P)
if(M.count(now)) return i*m+M[now];
}
int gcd(int a,int b){ return b?gcd(b,a%b):a; }
int Calc(int A,int B,int p,int a){
int ind_B=getInd(B,p,a), phi_P=Pow(p,a-1)*(p-1); //printf("indB=%d\n",ind_B);
int d=gcd(A,phi_P);
if(ind_B%d) return 0;
return d;
}
int Solve(int A,int B,int p,int a){ //printf("%d^%d\n",p,a);
int d=Count(p,B);
if(d>=a){
int t=(a-1)/A+1;
return Pow(p,a-t);
}
if(d%A) return 0;
return Calc(A,B,p,a-d)*Pow(p,d-d/A);
}
int _test,A,B,C,ans;
int main(){
freopen("bzoj2219.in","r",stdin);
freopen("bzoj2219.out","w",stdout);
int _test; scanf("%d",&_test);
while(_test--){
scanf("%d%d%d",&A,&B,&C); C=C*2+1;
ans=1;
for(int i=2;i*i<=C;i++)
if(C%i==0){
int t=0; while(C%i==0) t++, C/=i;
ans=ans*Solve(A,B,i,t);
}
if(C>1) ans=ans*Solve(A,B,C,1);
printf("%d\n",ans);
}
return 0;
}