本文主要是介绍sdut2165 Crack Mathmen （山东省第二届ACM省赛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文出自：http://blog.csdn.net/svitter，转载请注明出处。
原题：点击打开链接
和晨阳哥一同讨论了一下这个题目= =终于在今晚AC了。
这个题目可以说是RSA加密算法的变种。。
考虑997是素数，那么符合欧拉定理，然后想到费马小定理 m ^ 996 MOD 997 = 1;
因为一般的RSA解密算法都是C^d mod 997 = m 这种形式，苦思冥想了好久解密算法，仍然没有得到解决。
最后终于大彻大悟的明白：
呵呵，你想多了。。这个题目可以用打表过- -
要注意的问题：
1.加密码与原码是要一一对应，在原码中已经标出。
2.计算MOD幂的时候使用二分算法，如果不使用必然超时（n 可以取到 10 ^ 9)。这个算法依据pow算法得出。
/*author : Vit/csdn *from: http://blog.csdn.net/svitter *if you love it, please show the original site*/ #include <iostream>
#include <stdio.h>
#include <string.h>using namespace std;#define lln long long intchar str[1000010];
char key[1001];
lln ch[127];
lln n;
lln ans, tt, temp;bool get(lln &c)
{temp = c, ans = 1, tt = n;while(tt){if(tt &1)ans = (ans * temp) % 997;temp = temp * temp % 997;tt = tt >> 1;}if(ch[c] == -1)ch[c] = ans;
}bool init()
{lln i;memset(ch, -1, sizeof(ch));memset(key, '\0', sizeof(key));for(i = 32; i < 127; i++){if(get(i))continue;elsereturn false;}for(i = 32; i < 127; i++){lln &tmp = ch[i];if(key[tmp] == '\0')//检查码值相同的情况key[ch[i]] = (char)i;else{return false;}}return true;
}void ace()
{lln c, cur;lln length;lln i, l;char temp[400000];bool isstr;cin >> c;while(c--){while(cin >> n){memset(str, '\0', sizeof(str));scanf("%s", str);if(init()){l = 0;isstr = 1;//cout << key[590] << endl;length = strlen(str);for(i = 0; i < length; i += 3){cur = (str[i]-'0') *100 + (str[i+1]-'0') * 10 + str[i+2] - '0';if(key[cur] != '\0')//没有对应的翻译码temp[l++] = key[cur];else{isstr = false;break;}}if(isstr){for(i = 0; i < l; i++)cout << temp[i];cout << endl;}else{cout << "No Solution" << endl;}}else{cout << "No Solution" << endl;}}}
}int main()
{ace();return 0;
}
这篇关于sdut2165 Crack Mathmen （山东省第二届ACM省赛）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
