hdu 1211 2种解法 求逆元 水题

RSATime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 853    Accepted Submission(s): 632


Problem DescriptionInputOutputSample InputSample OutputAuthorSourceRecommend

题意：

输入数字 进行解码

解码方式  M = D(c) = cd mod n 对于输入的数c能够解码到M   M即使我们要的明文  按字符型输出  

另外 C = E(m) = me mod n 是加密方式 不用管它

输入p, q, e, l   那么可以得到n = p × q,  F(n) = (p - 1) × (q - 1)

 那么n知道 c是输入的  只要求出d就可以了

题设条件为d × e mod F(n) = 1 mod F(n),
即(d*e)%fn==1%fn

那么我可以很容易的根据这个式子 求出来d    第一种方法 直接暴力 第二种方法就是扩展欧几里得  

欧科  贴代码

#include<stdio.h>#include<math.h>int x,y;int GCD(int a,int b){__int64 t,d;if(b==0){x=1;y=0;return a;}d=GCD(b,a%b);t=x;x=y;y=t-(a/b)*(y);     return d;}int main(){int p,q,e,n,d,m,c,fn,i,j,t,gcd,k;while(scanf("%d %d %d %d",&p,&q,&e,&t)!=EOF)    {n=p*q;fn=(p-1)*(q-1);gcd=GCD(e,fn);//a,bd=x*(1/gcd);//d就是模板中的x0        k=d/(fn/gcd);d=d-k*(fn/gcd);if(d<0) d=d+fn/gcd;for(i=0;i<t;i++){scanf("%d",&c);m=1;for(j=0;j<d;j++){m*=c;m%=n;}printf("%c",m);}printf("\n");}return 0;}