Luogu P4358 密钥破解题解报告

题目传送门

【题目大意】

给定一个正整数N，可以被分解为两个不同的质数p和q，计算出r=(p-1)*(q-1)。

然后给出了一个小于r且与r互质的整数e，已知e*d≡1(mod r)，求d。

最后给定一个数c，求n=c^d%N

【思路分析】

这题总体来说思路真的很简单QWQ

首先既然是找因数，那么可以立刻想到Pollard-rho(其实只是因为这是一道Pollard-Rho的模板题)

然后求d的过程就是求e的乘法逆元嘛也很简单

最后求c^d，就很明显是快速幂了

于是就……over了！？

【代码实现】

放一波代码就走人吧

其实很玄学……我一开始只过了3个点，其他全部TLE，结果稍微改了一点就AC了

emmmm……好吧不是很懂，反正我已经AC了，下次不再用最开始那种做法就是了QAQ

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define RG register
 4 #define go(i,a,b) for(RG int i=a;i<=b;i++)
 5 using namespace std;
 6 ll fr(){
 7   ll w=0,q=1;
 8   char ch=getchar();
 9   while(ch<'0'||ch>'9'){
10     if(ch=='-') q=-1;
11     ch=getchar();
12   }
13   while(ch>='0'&&ch<='9')
14     w=(w<<1)+(w<<3)+ch-'0',ch=getchar();
15   return w*q;
16 }
17 ll e,N,c,p,q,r;
18 ll gcd(ll x,ll y) {return y==0?x:gcd(y,x%y);}
19 ll mul(ll x,ll y){//快速乘(类似于快速幂的东东)
20   if(y==0||x==0) return 0;
21   ll ans=0;
22   while(y){
23     if(y&1) ans+=x,ans%=N;
24     x=(x<<1)%N;y>>=1;
25   }
26   return ans;
27 }
28 ll count(ll x,ll y) {return (mul(x,x)+y)%N;}
29 void Pollard_Rho(){
30   ll cc=rand()%N+1;
31   ll x1,x2,d;
32   x1=x2=rand()%N+1;
33   while(1){
34     x1=count(x1,cc);x2=count(count(x2,cc),cc);
35     if(x1==x2) {x1=x2=rand()%N+1;cc=rand()%N+1;}
36     d=gcd(abs(x2-x1),N);
37     if(d>1&&d<N){p=d;q=N/p;return;}
38   }
39   return;
40 }
41 ll exgcd(ll a,ll b,ll &x,ll &y){//求乘法逆元
42   if(b==0) {x=1;y=0;return a;}
43   ll d=exgcd(b,a%b,x,y);
44   ll z=x;x=y;y=z-y*(a/b);
45   return d;
46 }
47 ll ksm(ll x,ll y){
48   ll ans=1,num=x;
49   while(y){
50     if(y&1) ans=mul(ans,num)%N;
51     num=mul(num,num)%N;
52     y>>=1;
53   }
54   return ans;
55 }
56 int main(){
57   srand(time(0));//这个是取随机数之前一定要写的东东QAQ
58   e=fr();N=fr();c=fr();
59   Pollard_Rho();
60   r=mul(p-1,q-1);
61   ll d,D;exgcd(e,r,d,D);
62   while(d<=0) d+=r;
63   ll n=ksm(c,d);
64   cout<<d<<" "<<n<<endl;
65   return 0;
66 }

点击看玄学代码

Luogu P4358 密钥破解 题解报告

Luogu P4358 密钥破解题解报告