RSA

///@author Sycamore, ZJNU;
///@date 8/4/2017
#include<iostream>
using namespace std;
typedef long long ll;
ll mod(ll a, ll b)
{
	return ((a%b) + b) % b;
}
ll extended_euclid(ll a, ll b, ll &x, ll &y)
{
	ll xx = y = 0;
	ll yy = x = 1;
	while (b)
	{
		ll q = a / b;
		ll t = b;
		b = a%b;
		a = t;
		t = xx;
		xx = x - q*xx;
		x = t;
		t = yy;
		yy = y - q*yy;
		y = t;
	}
	return a;
}
 
 
ll mod_inverse(ll a, ll n)
{
	ll x, y;
	ll g = extended_euclid(a, n, x, y);
	if (g > 1) return -1;
	return mod(x, n);
}
 
ll powermod(ll a, ll b, ll m)
{
	ll ret = 1;
	while (b)
	{
		if (b & 1) ret = ret*a%m;
		a = (a*a) % m;
		b >>= 1;
	}
	return ret;
}
int main()
{
	ios::sync_with_stdio(false);
	ll p, q, e, l;
	int c;
	while (cin >> p >> q >> e >> l)
	{
		ll n = p*q, F = (p - 1)*(q - 1), d = mod_inverse(e, F);
		while (l--)
		{
			cin >> c;
			cout << (char)powermod(c, d, n);
		}
		cout << ‘\n‘;
	}
	return 0;
}

HDU 1211: RSA

原文：http://www.cnblogs.com/zjnu/p/7295124.html