发布时间: 2017年7月9日 18:17 最后更新: 2017年7月9日 21:04 时间限制: 1000ms 内存限制: 128M
描述
近日来勒索病毒的事件频繁发生，小Y对它的加密原理非常感兴趣，研究了一番相关知识之后，他就来给你看他的加密程序，并给你一段密文，和你炫耀说就算把程序给你看你也破解不出来。
你扫了一眼代码发现加密的公式为b=ae%m ，其中e 是质数。
进一步分析发现m=p∗q ，p 和q 都为质数，p!=q ，
作为一个计算机高手，你早就对加密算法烂熟于心，一眼就看出这个程序的算法和原理，找到了破解的方法，发现小Y疏忽在与给了你一个不够大的m 。
你知道解密的公式与加密对称，为a=bd%m 。
但是你仍然无法心算解出这个d ，因此你需要借助计算机来将密文破解。
输入
第一行有一个整数T 表示数据组数。（T<=100 ）
接着有T 组数据，每组数据两行。
第一行有四个数e 、p 、q 和n ，其中e 、p 、q 如题所描述，n 表示需要解密的数字序列长度。
第二行是需要解密的数字序列a1..an 。
1 < p ,q ,e <= 108 ，p 、q 、e 为质数且p!=q 。
$0<=a_i<=i<=n$)< br=""> 保证解密的结果即原数列的值小于min(p,q) 并大于等于0
1<=n<=100
保证m 有且仅有两个不同的质因数p 和q ，并且一定存在一个题中描述的参数d 使得解密公式能够无损解密出所有0 ~min(p,q)−1 范围之间的数字。</M$。($1<=I<=N$)<>
输出
对于每组数据输出一行，表示解密后的数字序列，数字之间以空格隔开。
样例输入1 复制
1 5 19 29 3 335 440 514
样例输出1
65 67 77
这题是RSA加密解密算法，比赛的时候自信写了，感觉一定过，结果错了。。。。Orz还一直卡卡交不上去。（注意大整数溢出就好了）
涉及的内容大概就是计算逆元和快速幂，需要注意的是LL乘也会溢出，所以要处理乘。
#include <iostream> #include <stdio.h> using namespace std; typedef long long LL; LL e,p,q,n; int T; void extra_gcd(LL a, LL b, LL &x, LL &y, LL &d) { if(b == 0) { d = a; x = 1; y = 0; } else { extra_gcd(b, a%b, y, x, d); y -= (a/b) * x; } } LL multi_mod(LL a, LL n, LL mod) { LL ans = 0; while(n) { if(n & 1) { ans += a; if(ans > mod) ans -= mod; } n >>= 1; a <<= 1; if(a > mod) a-= mod; } return ans; } LL quick_mod(LL a,LL n,LL mod) { LL ans = 1; while(n) { if(n & 1) ans = multi_mod(ans, a, mod); a = multi_mod(a, a, mod); n >>= 1; } return ans; } int main() { scanf("%d", &T); while(T--) { scanf("%lld%lld%lld%lld",&e,&p,&q,&n); LL m=(p-1)*(q-1); LL y = p*q; LL d, o, l; extra_gcd(e, m, d, o, l); d = ((d%m)+m)%m; for(LL i = 0; i < n; i++) { LL tmp; scanf("%lld", &tmp); tmp %= y; if(i) printf(" "); printf("%lld",quick_mod(tmp,d,y)); } printf(" "); } return 0; }