1 //0MS    236K    1318 B    G++
 2 /*
 3 
 4     题意：
 5         RSA密码加解密法的解密
 6     
 7     模拟题：
 8         可以算水题，不过也磨了挺久，一是逆元求法不明确，
 9     二是O(lgn)的n次方模数算法忘了，三是没注意64位，
10     还有电脑有点卡！！郁闷 
11 
12 */
13 #include<stdio.h>
14 #include<string.h>
15 /***************************************
16 函数：ExGcd 
17 功能：求两个数的最大公约数和模P的乘法逆元。
18 输入：a,b 输入参数，求这两个数的最大公约数
19    和a模b的逆元 或 b模a的逆元。
20 输出：x,y 分别表示a模b的逆元和b模a的逆元。
21 返回：r 表示a b 的最大公约数。
22 *************************************/
23 __int64 Exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y)
24 {
25     if(b==0){
26         x=1;
27         y=0;
28         return a;
29     }
30     __int64 r=Exgcd(b,a%b,x,y);
31     __int64 t=x;
32     x=y;
33     y=t-a/b*y;
34     return r;
35 } 
36 __int64 fac(__int64 a,__int64 d,__int64 n)
37 {
38     a%=n;
39     int t=1;
40     while(d){
41         if(d%2) t=(t*a)%n; 
42         a=(a*a)%n;
43         d/=2;
44     }
45     return t;
46 }
47 int main(void)
48 {
49     __int64 p,q,e;
50     __int64 l,a;
51     while(scanf("%I64d%I64d%I64d%I64d",&p,&q,&e,&l)!=EOF)
52     { 
53         char c[105];
54         memset(c,0,sizeof(c));
55         __int64 d1=0,d2=0;
56         __int64 n=p*q;
57         Exgcd(e,(p-1)*(q-1),d1,d2);
58         d1=(d1+(p-1)*(q-1))%((p-1)*(q-1));
59         //printf("%d %d",d1,d2); 
60         for(int i=0;i<l;i++){
61             scanf("%I64d",&a);
62             a=fac(a,d1,n);
63             int b=a;
64             c[i]=b;
65             //printf("%d %d %c\n",a,c[i],c[i]);
66         }
67         puts(c);
68     }
69     return 0;
70 }