BZOJ 2219 -- 数论之神

发表于 | 更新于 | 分类于 | 评论数：

摘要

求 $x^a=b\mod (2k+1)$ 的解数

第一步显然是将 $2k+1$ 质因数分解

题面

解

$$
2k+1=\prod p_i^{c_i}
$$

答案即为各方程 $x^a=b\mod p_i^{c_i}$ 的解数的积

分类讨论

最简单的是 $p^c|b$ 这意味着 $p^t|x^a$

其中 $t$ 为 ${\left \lfloor \frac {c-1}{a} \right \rfloor+1}$

解数即为 $p^{c-t}$

之后考虑 $\gcd (p^c, b)=1​$

求原根之后变成 $ax=b\mod m$

其中 $m=\varphi (p^c)$

最后是 $\gcd (p^c, b)>1$

记 $b=p^t\ast d$, $d\perp p$

易知 $a|t​$

之后扣掉 $p^t​$ ，记 $y=\frac {x}{p^{t/a}}​$

$y^a=d\mod p^{c-t}$

注意解出来个数还要乘 $p^{t-t/a}$

(拓模的范围，之后扣掉 $p|y$ )

(有趣的是 $y$ 解出来自然不是 $p$ 的倍数)

Pickupwin: 听说保证有解……

Code

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
74
75
76
#include <cstdio>

int Test;
int A, B, K;

int Pri[33], Tim[33], Val[33], Cnt;

int gcd(int a, int b){
	return b==0?a:gcd(b, a%b);
}

int count(int n, int p){
	int ret=0;
	while(n%p==0)	{n/=p;++ret;}
	return ret;
}

int pow(int p, int c){
	int ret=1;
	for(int i=0;i<c;++i)	ret*=p;
	return ret;
}

void Split(int v){
	Cnt=0;
	for(int i=2, c;1LL*i*i<=(long long)(v);++i){
		c=0;
		while(v%i==0)	{v/=i;++c;}
		if(c){
			++Cnt;
			Pri[Cnt]=i;
			Tim[Cnt]=c;
		}
	}
	if(v>1){
		++Cnt;
		Pri[Cnt]=v;
		Tim[Cnt]=1;
	}
	for(int i=1;i<=Cnt;++i){
		Val[i]=1;
		for(int j=0;j<Tim[i];++j)	Val[i]*=Pri[i];
	}
}

int Phi(int v, int p){
	if(v%p==0)	{v/=p;v*=(p-1);}
	return v;
}

int main(){
	
	scanf("%d", &Test);
	
	while(Test--){
		
		scanf("%d%d%d", &A, &B, &K);
		
		Split((K<<1)|1);
		
		int Ans=1;
		for(int i=1;i<=Cnt;++i){
			if(gcd(Val[i], B)==1)	Ans*=gcd(A, Phi(Val[i], Pri[i]));
			else if(B%Val[i]==0)	Ans*=pow(Pri[i], Tim[i]-((Tim[i]-1)/A+1));
			else{
				int t=count(gcd(Val[i], B), Pri[i]);
				Ans*=gcd(A, Phi(pow(Pri[i], Tim[i]-t), Pri[i]))*pow(Pri[i], t-t/A);
			}
		}
		
		printf("%d\n", Ans);
	}
	
	
	return 0;
}