BZOJ 4522 密钥破解

发表于 | 更新于

Link

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
#include "lucida"
using std::pair;
using std::swap;
/*int64 mul(int64 x,int64 times,int64 modu) {
	if(x<times) swap(x,times);
	int64 res;
	for(res=0;times;(x+=x)%=modu,times>>=1)
		if(times&1) (res+=x)%=modu;
	return res;
}*/
int64 mul(int64 a,int64 b,int64 modu)
{
    int64 temp=a*b-(int64)((long double)a/modu*b+1e-8)*modu;
    if (temp<0) temp+=modu;
    return temp;
}
int64 pow(int64 base,int64 index,int64 modu) {
	int64 res;
	for(res=1;index;base=mul(base,base,modu),index>>=1)
		if(index&1) res=mul(res,base,modu);
	return res;
}
int64 exgcd(int64 a,int64 b,int64 &x,int64 &y) {
	if(!b) {
		x=1,y=0;
		return a;
	} else {
		int64 d=exgcd(b,a%b,x,y);
		swap(x,y);y-=(a/b)*x;
		return d;
	}
}
int64 gcd(int64 a,int64 b) {
	a=a<0?-a:a;b=b<0?-b:b;
	for(int64 t;b;t=a%b,a=b,b=t);
	return a;
}
int64 FindDivisor(int64 x) {
	int64 c=rand()%(x-1)+1,d;
	for(int64 p2=rand()%x,p1=(mul(p2,p2,x)+c)%x,s=1,k=2;(d=gcd(p1-p2,x))==1;p1=(mul(p1,p1,x)+c)%x,++s)
		if(s==k) {
			p2=p1;
			k<<=1;
		}
	return d;
}
pair<int64,int64> Divide(int64 x) {
	int64 res;
	while((res=FindDivisor(x))==x);
	return pair<int64,int64>(res,x/res);
}
int main() {
	freopen("input","r",stdin);
	int64 e,N,c;is>>e>>N>>c;
	pair<int64,int64> pq=Divide(N);
	int64 r=(pq.first-1)*(pq.second-1);
	int64 x,y,gcd=exgcd(e,r,x,y);
	assert(gcd==1);
	int64 d=(x%r+r)%r,n=pow(c,d,N);
	os<<d<<' '<<n<<'\n';
	return 0;
}