hdu 1211 RSA

本文主要是介绍hdu 1211 RSA，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

主题思想： 数学题， 扩展欧几里得算，就线性同余方程。

d=gcd(a,b）可以得到， d=ax+by
ax+by=gcd(a,b) 依据扩展欧几里得可以求出系数，x,y ，注意,x,y可能小于0,

a*dmod b=gcd(a,b)=1
特别的如果gcd(a,b) 等于1,则 是，a模b的乘法逆元。
参考博客：
http://www.tuicool.com/articles/mINrQn

http://www.xuebuyuan.com/1394391.html
扩展欧几里得代码：

LL  extentGcd(LL a, LL b,LL &x,LL & y){if(b==0){x=1;y=0;return a;}LL gcd=extentGcd(b,a%b,x,y);LL t=x;x=y;y=t-a/b*y;return gcd;}

AC代码：

#include <iostream>
#include<cstdio>using namespace std;typedef long long   LL;LL  extentGcd(LL a, LL b,LL &x,LL & y){if(b==0){x=1;y=0;return a;}LL gcd=extentGcd(b,a%b,x,y);LL t=x;x=y;y=t-a/b*y;return gcd;}LL quickMulti(LL c,LL d,LL mod){LL ans=1;while(d){if(d%2==1)  ans=ans*c%mod;c=c*c%mod;d/=2;}return ans;}LL p,q,e,l,c,M;
LL n,f,pd;
int main ()
{LL x, y, d, a, b ;while (scanf ("%I64d%I64d%I64d%I64d", &p, &q, &e, &l) != EOF){n = p * q ;f = (p-1) * (q-1) ;extentGcd(e, f, x, y) ;pd = (x % f + f) % f ;for (int i = 0; i < l; i ++){scanf ("%I64d", &c) ;M = quickMulti(c, pd, n) ;printf ("%c", char(M)) ;}printf ("\n") ;}return 0 ;
}

这篇关于hdu 1211 RSA的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---