标题来源：

意甲冠军：给你e n c 并有m^e = c(mod n) 求 m

思路：首先学习RSA算法  

过程大致是

1.发送的信息是m

2.随机选择两个质数 p和q, n = q*p, n的欧拉函数值φ(n）= (p-1)*(q-1)这个须要证明 

3.选择一个与φ(n)互质的而且小于φ(n)的数e, 计算c = m^e(mod n)

4.发送c

5解密 求e的逆元d 逆元就是2个数乘一下在mod一个数等于1 这里就是e*d = 1(mod φ(n))

求逆元用扩展欧几里德或者直接求高速幂

6.计算c^d(mod n) 就是m

#include 
    
     #include 
     
      #include 
      
       using namespace std;//返回a^p mod n 高速幂int pow_mod(int a, int p, int n){	int ans = 1;	while(p)	{		if(p&1)		{			ans *= a;			ans %= n;		}		a *= a;		a %= n;		p >>= 1;	}	return ans;}bool prime(int x){	for(int i = 2; i*i <= x; i++)	{		if(x%i == 0)			return false;	}	return true;}int main(){		int T;	scanf("%d", &T);	while(T--)	{		int e, n, c;		scanf("%d %d %d", &e, &n, &c);		int p, q;		for(int i = 2; i*i <= n; i++)		{			if(n%i == 0 && prime(i) && prime(n/i))			{				p = i;				q = n/i;				break;			}		}				int x = (p-1)*(q-1), y = x;		for(int i = 2; i*i <= n; i++)		{			if(x % i == 0)			{				y = y / i * (i-1);				while(x % i == 0)					x /= i;			}		}		if(x > 1)			y = y / x * (x-1);		int inv = pow_mod(e, y-1, (p-1)*(q-1));		printf("%d\n", pow_mod(c, inv, n));	}	return 0;}