Luogu P4358 密钥破解 题解报告

题目传送门

【题目大意】

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

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

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

【思路分析】

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

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

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

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

于是就……over了！？

【代码实现】

放一波代码就走人吧

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

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

 #include<bits/stdc++.h>

 #define ll long long

 #define RG register

 #define go(i,a,b) for(RG int i=a;i<=b;i++)

 using namespace std;

 ll fr(){

   ll w=,q=;

   char ch=getchar();

   while(ch<''||ch>''){

     if(ch=='-') q=-;

     ch=getchar();

   }

   while(ch>=''&&ch<='')

     w=(w<<)+(w<<)+ch-'',ch=getchar();

   return w*q;

 }

 ll e,N,c,p,q,r;

 ll gcd(ll x,ll y) {return y==?x:gcd(y,x%y);}

 ll mul(ll x,ll y){//快速乘(类似于快速幂的东东)

   if(y==||x==) return ;

   ll ans=;

   while(y){

     if(y&) ans+=x,ans%=N;

     x=(x<<)%N;y>>=;

   }

   return ans;

 }

 ll count(ll x,ll y) {return (mul(x,x)+y)%N;}

 void Pollard_Rho(){

   ll cc=rand()%N+;

   ll x1,x2,d;

   x1=x2=rand()%N+;

   while(){

     x1=count(x1,cc);x2=count(count(x2,cc),cc);

     if(x1==x2) {x1=x2=rand()%N+;cc=rand()%N+;}

     d=gcd(abs(x2-x1),N);

     if(d>&&d<N){p=d;q=N/p;return;}

   }

   return;

 }

 ll exgcd(ll a,ll b,ll &x,ll &y){//求乘法逆元

   if(b==) {x=;y=;return a;}

   ll d=exgcd(b,a%b,x,y);

   ll z=x;x=y;y=z-y*(a/b);

   return d;

 }

 ll ksm(ll x,ll y){

   ll ans=,num=x;

   while(y){

     if(y&) ans=mul(ans,num)%N;

     num=mul(num,num)%N;

     y>>=;

   }

   return ans;

 }

 int main(){

   srand(time());//这个是取随机数之前一定要写的东东QAQ

   e=fr();N=fr();c=fr();

   Pollard_Rho();

   r=mul(p-,q-);

   ll d,D;exgcd(e,r,d,D);

   while(d<=) d+=r;

   ll n=ksm(c,d);

   cout<<d<<" "<<n<<endl;

   return ;

 }

点击看玄学代码