首页 > 代码库 > HDU 1211

HDU 1211

水。模拟即可。使用EXGCD求逆元

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL __int64using namespace std;LL p,q,e,n,f,d;void exgcd(LL a,LL b,LL &x,LL &y){	if(b==0){		x=1; y=0;		return ;	}	exgcd(b,a%b,x,y);	LL tmp=x;	x=y;	y=tmp-(a/b)*y;}LL quick(LL a,LL b,LL m){	a%=m;	LL ans=1;	while(b){		if(b&1)		ans=(ans*a)%m;		b>>=1;		a=(a*a)%m;	}	return ans;}int main(){	LL l,num;	LL x,y;	while(scanf("%I64d%I64d%I64d%I64d",&p,&q,&e,&l)!=EOF){		n=p*q; 		f=(p-1)*(q-1);		exgcd(e,f,x,y);		x=(x%f+f)%f;		for(LL i=1;i<=l;i++){			scanf("%I64d",&num);			int ans=(int)quick(num,x,n);			printf("%c",ans);		}		printf("\n");	}	return 0;}

  

HDU 1211