题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=1930
题目概述:
对于一个字符串,将字符串每三个字符进行编码,规则是将这三个字符转成对应的数字,字母A与1对应,B与2对应,C与3对应,以此类推,空格字符与27对应,转换完之后将这三个数字接在一起删掉前导零之后成为一个新数字,如:THE--->200805
之后给出四个秘钥(就是四个数字),将之前得到的数字分别对这四个秘钥取模,结果用上述方法同样转换成一个新数字,如四个数字为34, 81, 65, 43,取模结果为 1, 6, 20,38,则新数字即为1062038。
现在给出你四个秘钥以及n个经过上述转换后的数字,请你求出原字符串。(题意其实讲的不太好,没看懂的童鞋建议可以去看下原题面)
大致思路:
看懂题之后就是赤果果的中国剩余定理了,不过不保证秘钥之间不两两互素,所以用拓展之后的中国剩余定理。关于中国剩余定理就不赘述了(其实是窝自己也不太懂来着),细节见代码。
代码:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <vector> #include <ctime> #include <list> #include <map> #include <stack> #include <queue> #include <cstring> #include <algorithm> using namespace std; #define sacnf scanf #define scnaf scanf #define scanfi(x) scanf("%d",&x) #define scanfd(x) scanf("%lf",&x) #define scanfl(x) scanf("%lld",&x) #define scanfc(x) scanf("%c",&x) #define scanfs(x) scanf("%s",x) #define maxn 10 #define maxm 200 #define inf 1061109567 #define Eps 0.00001 const double PI=acos(-1.0); #define mod 1000000007 #define MAXNUM 10000 void Swap(int &a,int &b) {int t=a;a=b;b=t;} int Abs(int x) {return (x<0)?-x:x;} typedef long long ll; typedef unsigned int uint; ll a[maxn],m[maxn]; char t[maxm]; void init() { for(int i=1;i<=27;i++) t['A'+i]=i; } ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} ll ex_gcd(ll a,ll b,ll &x,ll &y) { if(b==0) {x=1;y=0;return a;} ll ans=ex_gcd(b,a%b,x,y); ll temp=x;x=y;y=temp-(a/b)*y; return ans; } ll Inv(ll a,ll b) { ll x,y,d; d=ex_gcd(a,b,x,y); return (d!=1)?-1:(x%b+b)%b; } bool Merge(ll a1,ll m1,ll a2,ll m2,ll &a3,ll &m3) { ll d=gcd(m1,m2),c=a2-a1; if(c%d) return false; c=(c%m2+m2)%m2; m1/=d;m2/=d;c/=d; c*=Inv(m1,m2); c%=m2;c*=m1*d;c+=a1; m3=m1*m2*d; a3=(c%m3+m3)%m3; return true; } ll CRT(int n) { ll a1=a[1],m1=m[1]; for(int i=2;i<=n;i++) { ll a2=a[i],m2=m[i],m3, a3; if(!Merge(a1,m1,a2,m2,a3,m3)) return -1; a1=a3;m1=m3; } return (a1%m1+m1)%m1; } /*ll CRT(int n) { ll M=1,ans=0; for(int i=1;i<=n;i++) M*=m[i]; for(int i=1;i<=n;i++) { ll x,y,Mi=M/m[i]; ex_gcd(Mi,m[i],x,y); ans=(ans+Mi*x*a[i])%M; } return (ans<0)?ans+M:ans; }*/ void solve(ll x) { int temp,cnt=4; for(int i=1;i<=4;i++) { temp=x%10;x/=10; temp+=(x%10)*10;x/=10; a[cnt--]=temp; } x=CRT(4);cnt=3; for(int i=1;i<=3;i++) { temp=x%10;x/=10; temp+=(x%10)*10;x/=10; a[cnt--]=temp; } } int main() { //freopen("data.in","r",stdin); //freopen("data.out","w",stdout); //clock_t st=clock(); int T;scanf("%d",&T); init(); while(T--) { int n;scanf("%d",&n); for(int i=1;i<=4;i++) scanf("%lld",&m[i]); for(int i=1;i<=n;i++) { ll x;scanf("%lld",&x); solve(x); int cnt=3; if(i==n) while(cnt>0&&a[cnt]==27) cnt--; for(int j=1;j<=cnt;j++) printf("%c",(a[j]==27)?' ':(char)(a[j]-1+'A')); } printf(" "); } //clock_t ed=clock(); //printf(" Time Used : %.5lf Ms. ",(double)(ed-st)/CLOCKS_PER_SEC); return 0; }