hdu1211（RSA）（扩展欧几里得+快速幂+快速乘）

2019-04-13 21:42发布

站内文章 / 模拟电子
14748 0 1772
其实题意可以这样理解，已知e，n，F(n)，且gcd（e,F(n)）=1
求d使得
d*e = 1 mod F(n)。
由扩展欧几里得算法可求出d。
然后给一个整数an，输出
(an)^d (mod n)的对应的字符。（显然快速幂搞定） #include #include #include using namespace std; typedef long long ll; ll gcd_ex(ll a,ll b,ll &x,ll &y) { if(!b) {x=1;y=0;return a;} ll d=gcd_ex(b,a%b,y,x); y-=a/b*x; return d; } ll quick_mul(ll a,ll b,ll m) { ll res=0; a%=m,b%=m; while(b>0) { if(b&1) res=(res+a)%m; b>>=1; a=(a<<1)%m; } return res; } ll quick_pow(ll a,ll b,ll m) { ll res=1; a%=m; while(b>0) { if(b&1) res=quick_mul(res,a,m); b>>=1; a=quick_mul(a,a,m); } return res; } int main(int argc, char const *argv[]) { int p,q,e,l; while(scanf("%d %d %d %d",&p,&q,&e,&l)!=EOF) { ll n=(ll)p*(ll)q,fn=(ll)(p-1)*(ll)(q-1),x,y; gcd_ex((ll)e,fn,x,y); x=(x%fn<0)?(x%fn+fn):x%fn; while(l--) { scanf("%lld",&y); printf("%c",(char)quick_pow(y,x,n) ); } putchar(' '); } return 0; }

热门文章