题面

RSA是一种加密工具。

• 选择两个素数$p,q$。
• 计算$n=p \times q$，$f(n)=(p-1) \times (q-1)$。
• 选择一个整数$e \in (1,f(n))$,使得$gcd(e,f(n))=1$,$e$是公钥。
• 计算$d$使得$d \times e \equiv 1 \pmod {f(N)}$。

如果解密的话使用如下方法：
$$M=D(c)=c^d \% n$$
$c$是一种ASCII的值，请把密文翻译成明文。

题解

计算$n,F(n)$用扩展欧几里得求出$d$，最后根据公式求明文。

代码

#include 
using namespace std;
int a,b,x,y,k;
void exgcd(int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    k=x;
    x=y;
    y=k-a/b*y;
    return;
}
int mul(int x, int y, int mod)
{
    int res = 1;
    while(y)
    {
        if(y & 1)
            res = ((res % mod) * (x % mod)) % mod;
        x = ((x % mod) * (x % mod)) % mod;
        y >>= 1;
    }
    return res;
}
int main(){
    int p,q,e,t,n,fn,d;
    ios::sync_with_stdio(false);
    while(cin>>p>>q>>e>>t){
        n=p*q;
        fn=(p-1)*(q-1);
        exgcd(e,fn);
        d=(x+fn)%fn;
        while(t--){
            int a;
            cin>>a;
            cout<