题目：http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2165&cid=1431
快速幂。
#include <iostream> #include <string.h> #include <stdlib.h> #include <stdio.h> #include <queue> #include <vector> #include <algorithm> #include <queue> #define inf 0x3f3f3f3f typedef long long ll; using namespace std; int tt,n,cn[110]; int qq[100010],we; struct node { int w,id; }q[110]; #define mod 997 int er(int lf,int rf,int key) { int l=lf,mid; int r=rf; while(l<=r) { mid = l+(r-l)/2; if(q[mid].w==key) return mid; else if(q[mid].w>key) { r=mid-1; } else { l=mid+1; } } return -1; } int cmp(const void *a,const void *b) { struct node *aa=(struct node *)a; struct node *bb=(struct node *)b; return aa->w-bb->w; } int mult_mod(int a,int b)//计算 (a*b)%c. { a%=mod;// 利用二分思想减少相乘的时间 b%=mod; ll ret=0; while(b) { if(b&1) { ret+=a; ret%=mod; } a<<=1; if(a>=mod) a%=mod; b>>=1; } return ret; } int pow_mod(int x,int n)//x^n%n { if(n==1) return x%mod; x%=mod; int tmp=x; int ret=1; while(n) { if(n&1) ret=mult_mod(ret,tmp); tmp=mult_mod(tmp,tmp); n>>=1; } return ret; } void init() { memset(cn,0,sizeof(cn)); tt=0; for(int i=48;i<=57;i++) { q[tt].id=i; q[tt++].w=pow_mod(i,n); } for(int i=65;i<=90;i++) { q[tt].id=i; q[tt++].w=pow_mod(i,n); } for(int i=97;i<=122;i++) { q[tt].id=i; q[tt++].w=pow_mod(i,n); } qsort(q,tt,sizeof(q[0]),cmp); cn[0]=1; for(int i=1;i<tt;i++) { if(q[i].w==q[i-1].w) { cn[i]=2; cn[i-1]=2; } else cn[i]=1; } } char s[1000010]; int main() { int T,da; bool FF; scanf("%d",&T); for(int z=1;z<=T;z++) { FF=true; scanf("%d",&n); init(); we=0; scanf("%s",s); int l=strlen(s); for(int i=0;i<l;i=i+3) { da=s[i]-'0'; for(int j=i+1;j<=i+2;j++) { da=da*10+(s[j]-'0'); } int t=er(0,tt-1,da); if(t==-1||cn[t]>1) { printf("No Solution "); FF=false; break; } else { qq[we++]=q[t].id; } } if(FF) { for(int i=0;i<we;i++) printf("%c",qq[i]); printf(" "); } // printf(" "); } return 0; }