hdu 1211 RSA

// 表示题目意思我是理解了蛮久 英语太水了 
//首先这是解密公式 m=c^d mod n
// 给你 p q e 然后 n=p*q fn=(p-1)*(q-1)
// 给你 e,根据公式 e*d mod fn =1 求出 d 
// 然后有 L个数据要解密
// 算法：
// 扩展欧几里得 ：求 d
// 快速幂运算   ：解密
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define maxm 100010
#define maxn 1000110
#define LL __int64
LL pow(LL a,LL b,int m){
   LL t=1;
   for(;b>0;b=b>>1,a=(a*a)%m)
      if(b&1) t=(t*a)%m;
   return t;
}
LL d,x,y;
void extendGcd(LL a,LL b){
    if(b==0){
        d=a;
        x=1;
        y=0;
    }
    else{
        extendGcd(b,a%b);
        LL tp=x;
        x=y;
        y=tp-a/b*y;
    }
}
int main()
{
    int cc;
    char ch;
    LL p,q,e,l,fn,n;
    while(scanf("%I64d %I64d %I64d %I64d",&p,&q,&e,&l)!=EOF){
        fn=(q-1)*(p-1);
        n=p*q;
        extendGcd(e,fn);
        while(x<0) x+=fn/d;
         //printf("%I64d",x);
        while(l--){
            scanf("%d",&cc);
            ch=(char)(pow(cc,x,n));
            printf("%c",ch);
        }
        printf("
");
    }
    //printf("%I64d %I64d
",x,y);
    return 0;
}