<题目链接>
<转载于 >>> >
题目大意：
RSA是个很强大的加密数据的工具，对RSA系统的描述如下：
选择两个大素数p、q，计算n = p * q，F(n) = (p-1)*(q-1)，选择一个整数e，使得gcd(e，F(n)) = 1，
e是公匙，计算d使得d * e mod F(n) = 1 mod F(n)，d是私匙。加密数据的方法为
C = E(m) = m^e mod n
解密数据的方法为
M = D(c) = c^d mod n
其中，c是密文中字母的ASCII的值；m是明文中字母的ASCII的值。
现在问题来了，给你p、q、e和一些密文，请把密文翻译成明文。
解题分析：
根据p和q，计算出n = p * q，F(n) = (p-1)*(q-1)，用扩展欧几里得方法求出e关于F(n)的逆元d，根据
公式 M= c^d mod n，解出明文。
#include <cstdio> #define ll long long ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (!b)
{
x = ; y = ;
return a;
}
ll R = exgcd(b, a%b, y, x);
y -= a / b * x;
return R;
} ll pow(ll a, ll b,ll mod)
{
ll ans = ;
while (b)
{
if (b & )
{
ans = (ans*a) % mod;
}
b >>= ;
a = (a*a) % mod; }
return ans;
} int main()
{
ll q, p, e, l;
while (scanf("%lld %lld %lld %lld", &p, &q, &e, &l) != EOF)
{
ll n = q * p;
ll fn = (q-)*(p-); ll d, y;
ll gcd=exgcd(e, fn, d, y); d = (d%fn + fn) % fn; //用扩展欧几里得方法求出e关于F(n)的逆元d for (ll i = ; i < l; i++)
{
ll cal; scanf("%lld", &cal); ll ans = pow(cal, d,n);
printf("%c", ans%); //注意，这里是 %128
}
printf("\n");
}
return ;
}
2018-08-12