RSA

101 103 7 11
7716 7746 7497 126 8486 4708 7746 623 7298 7357 3239

I-LOVE-ACM.

//0MS	228K
#include<stdio.h>
#include<math.h>
int p,q,e,l;
int exgcd(int A,int &x,int B,int &y)
{
    int x1,y1,x0,y0;
    x0=1;y0=0;
    x1=0;y1=1;
    int r=(A%B+B)%B;
    int q=(A-r)/B;
    x=0;y=1;
    while(r)
    {
        x=x0-q*x1;
        y=y0-q*y1;
        x0=x1;
        y0=y1;
        x1=x;y1=y;
        A=B;B=r;r=A%B;
        q=(A-r)/B;
    }
    return B;
}
int multi(int a,int b,int m)//a*b%m
{
    int ret=0;
    while(b>0)
    {
        if(b&1)ret=(ret+a)%m;
        b>>=1;
        a=(a<<1)%m;
    }
    return ret;
}
int quick_mod(int a,int b,int m)//a^b%m
{
    int ans=1;
    a%=m;
    while(b)
    {
        if(b&1)
        {
            ans=multi(ans,a,m);
            b--;
        }
        b/=2;
        a=multi(a,a,m);
    }
    return ans;
}
int main()
{
    while(scanf("%d%d%d%d",&p,&q,&e,&l)!=EOF)
    {
        int n=p*q,d,x,y,a;
        p=(p-1)*(q-1);
        d=exgcd(e,x,p,y);//解线性同余方程e*x=b(mod p)
        x=(x%(p/d)+p/d)%(p/d);//求最小的解x
        for(int i=0;i<l;i++)
        {
            scanf("%d",&a);
            printf("%c",quick_mod(a,x,n));
        }
        printf("\n");
    }
    return 0;
}