第二届山东省ACM省赛回顾 Crack Mathmen(打表)


Crack Mathmen

题目链接:http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2165

Time Limit: 1000ms   Memory limit: 65536K  有疑问?点这里^_^

题目描写

 Since mathmen take security very seriously, they communicate in encrypted messages. They cipher their texts in this way: for every characther c in the message,
they replace c with f(c) = (the ASCII code of c)n mod 1997
 if f(c) < 10, they put two preceding zeros in front of f(c) to make it a three digit number; if 10 <= f(c) < 100, they
put one preceding zero in front of
 f(c) to make it a three digit number.

For example, if they choose n = 2 and the message is "World" (without quotation
marks), they encode the message like this:

1. the first character is ‘W’, and it’s ASCII code is 87. Then f(′W′) = 87^2 mod
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^2 mod
997 = 35. Since 10 <= f(′r′) < 100, they add a 0 in front and 
make it 035.

4. the forth character is ‘l’, and it’s ASCII code is 108. Then f(′l′) = 108^2 mod
997 = 697.

5. the fifth character is ‘d’, and it’s ASCII code is 100. Then f(′d′) = 100^2 mod
997 = 30. Since 10 <= f(′d′) < 100, they add a 0 in front and 
make it 030.

6. Hence, the encrypted message is "590357035697030".

One day, an encrypted message a mathman sent was intercepted by the human
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 contains a integer, indicating the number of test cases in the input. The first line of each
test case contains a non-negative integer n (n <= 10^9). The second line
 of each test case contains a string of digits. The length of the string is at most 10^6.

输出

 For each test case, output a line containing the plain text. If their are no or more than one possible plain text that can be encrypted as the input, then output
"No Solution" (without quotation marks).
 Since mathmen use only alphebetical letters and digits, you can assume that no characters other than alphebetical letters and digits may
occur in
 the plain text. Print a line between two test cases.

示例输入

3
2
590357035697030
0
001001001001001
1000000000
001001001001001

示例输出

World
No Solution
No Solution

第1行3,代表3组数据,然后每组输入两行 第1行是 n 第2行是要破译的密码;
把密码分成每3个数字1组,去破译

例如第1组样例 590357035697030 把它每3个拆成1组,每组翻译成1个字符,第1行输入的 n=2,代表该字符asc码的几次方
例如 590 = 87^2%997  , 'W的'asc码就是 87,, 所以第1个字母是 W,顺次类推输出了 World;
可以看出只要我们知道了asc码,我们就可以求出 对应的字符,很容易想到打表,由于题目说翻译后的密码只包括大小写字母和数字,数组不用开很大就可以贮存;
而 对求幂取模,,直接套用快速幂模板就好了。 No Solution的情况: 1:没有对应的字符 2:对应的字符多于1个
#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,'',sizeof(ar)); memset(str,'',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]=='') //用来标记是不是有重复的密码 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]; //每3个字符存到另外一个数组中,,固然也能够int res=(str[i]-'0')*100+(str[i+1]-'0')*10+str[i+2]-'0';更简单 } if(signaa) { printf("No Solution "); continue; } else { for(int i=1;i<=k;i++) { int res=atoi(test[i]); if(ar[res]!='') printf("%c",ar[res]); else { signaa=1; break; } } if(signaa) { printf("No Solution "); } else printf(" "); } } return 0; }



波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 第二届山东省ACM省赛回顾 Crack Mathmen(打表)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡