Crack Mathmen
题目链接：?action=showproblem&problemid=2165
Time Limit: 1000ms Memory limit: 65536K有疑问？点这里^_^题目描述
Since mathmen take security very seriously, they communicate in encryptedmessages. They cipher their texts in this way: for every characther c in themessage, they replace c with f(c) = (the ASCII code of c)n mod 1997if f(c) < 10, they put two preceding zeros in front of f(c) to make it a threedigit number; if 10 <= f(c) < 100, they put one preceding zero in front off(c) to make it a three digit number.
For example, if they choose n = 2 and the message is "World" (withoutquotation marks), they encode the message like this:
1. the first character is ‘W’, and it’s ASCII code is 87. Then f(′W′) = 87^2mod 997 = 590.
2. the second character is ‘o’, and it’s ASCII code is 111. Then f(′o′) =111^2 mod 997 = 357.
3. the third character is ‘r’, and it’s ASCII code is 114. Then f(′r′) = 114^2mod 997 = 35. Since 10 <= f(′r′) < 100, they add a 0 in front andmake it 035.
4. the forth character is ‘l’, and it’s ASCII code is 108. Then f(′l′) = 108^2mod 997 = 697.
5. the fifth character is ‘d’, and it’s ASCII code is 100. Then f(′d′) = 100^2mod 997 = 30. Since 10 <= f(′d′) < 100, they add a 0 in front andmake it 030.
6. Hence, the encrypted message is "590357035697030".
One day, an encrypted message a mathman sent was intercepted by thehuman being. As the cleverest one, could you find out what the plain text(i.e., the message before encryption) was?
输入
The input contains multiple test cases. The first line of the input containsa integer, indicating the number of test cases in the input. The first line ofeach test case contains a non-negative integer n (n <= 10^9). The second lineof each test case contains a string of digits. The length of the string is atmost 10^6.
输出
For each test case, output a line containing the plain text. If their are no ormore than one possible plain text that can be encrypted as the input, thenoutput "No Solution" (without quotation marks).Since mathmen use only alphebetical letters and digits, you can assumethat no characters other than alphebetical letters and digits may occur inthe plain text.Print a line between two test cases.
示例输入
3259035703569703000010010010010011000000000001001001001001
示例输出
WorldNo SolutionNo Solution第一行3，代表三组数据，然后每组输入两行 第一行是 n 第二行是要破译的密码；把密码分成每三个数字一组，去破译例如第一组样例 590357035697030 把它每3个拆成一组，每组翻译成一个字符，第一行输入的 n=2，代表该字符asc码的几次方例如 590 = 87^2%997 ， ‘W的’asc码就是 87，， 所以第一个字母是 W，依次类推输出了 World；可以看出只要我们知道了asc码，我们就能求出 对应的字符，，很容易想到打表，因为题目说翻译后的密码只包含大小写字母和数字，数组不用开很大就能储存；而 对于求幂取模，，直接套用快速幂模板就行了。 No Solution的情况： 1：没有对应的字符 2：对应的字符多于一个#include <stdio.h>#include <cmath>#include <cstring>#include <stdlib.h>typedef long long ll;const int maxn=1000000+10;char str[maxn];char test[maxn/3][5];char ar[1010];int signaa;ll pow_mod(ll x,ll n, ll mod) //快速幂模板{ll res=1;x=x%mod;while(n>0){if(n%2){res=res*x%mod;}x=x*x%mod;n/=2;}return res;}int main(){int n;scanf("%d",&n);int cas=0;while(n–){signaa=0;memset(ar,'\0',sizeof(ar));memset(str,'\0',sizeof(str));int t;scanf("%d",&t);getchar();int i;int res;for(int i=48;i<=122;i++){if((i>=48&&i<=57)||(i>=65&&i<=90)||(i>=97&&i<=122)){res=pow_mod(i,t,997);//输入了t之后，把求出的值储存到字符数组ar的坐标，把该位置的asc码转换成字符存到ac中if(ar[res]=='\0') //用来标记是否有重复的密码ar[res]=char(i);//把该位置的asc码转换成字符存到ac中else{signaa=1;//如果重复，标记变量变为1；break;}}}gets(str);int len=strlen(str);int k=0,s=0;for(int i=0;i<len;i++){if(i%3==0){k++;s=0;}test[k][s++]=str[i];//每三个字符存到另一个数组中，，当然也可以int res=(str[i]-'0')*100+(str[i+1]-'0')*10+str[i+2]-'0';更简单}if(signaa){printf("No Solution\n");continue;}else{for(int i=1;i<=k;i++){int res=atoi(test[i]);if(ar[res]!='\0')printf("%c",ar[res]);else{signaa=1;break;}}if(signaa){printf("No Solution\n");}elseprintf("\n");}}return 0;}
生活比你想象的要容易得多，只要学会接受那些不可接受的，
