版权声明：本文为博主原创文章，未经博主同意不得转载。 https://blog.csdn.net/svitter/article/details/24270265
本文出自：http://blog.csdn.net/svitter。转载请注明出处。
原题：点击打开链接
和晨阳哥一同讨论了一下这个题目=
=最终在今晚AC了。
这个题目能够说是RSA加密算法的变种。。
考虑997是素数，那么符合欧拉定理。然后想到费马小定理 m ^ 996 MOD 997 = 1;
由于一般的RSA解密算法都是C^d mod 997 = m 这样的形式，苦思冥想了好久解密算法，仍然没有得到解决。
最后最终大彻大悟的明确：
呵呵，你想多了。。这个题目能够用打表过- -
要注意的问题：
1.加password与原码是要一一相应，在原码中已经标出。
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 int
char 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;
else
return 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;
}