时间限制:0.5s
空间限制:6M
题意：
在b（2<b<36）进制中,找到所有长度为n（0<n<2000）的自守数k,满足k^2%b^n=k,字典序输出。
如 十进制中 9376^2 = 87909376 后面4位数都是9376.
Solution:
可以发现长度为n的满足要求的数中，其后n-1位也是自守数。
这样的数是很稀疏的，可以直接从n=1的情况开始搜索。当找到长度为n的数时记录，排序输出即可。
code
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int b, n;
struct node {
int s[2009];
bool operator < (const node &A) const {
for (int i = n; i > 0; i--) {
if (A.s[i] > s[i]) return 1;
if (A.s[i] < s[i]) return 0;
}
}
} a;
vector<node> ans;
void Find (int d, int k) {
if (k == n + 1) {
if (a.s[n] != 0||n==1) ans.push_back (a);
return ;
}
for (int i = 0; i < b; i++) {
int tem = d + (i * a.s[1] << 1);
for (int i = 2; i < k; i++)
tem += a.s[i] * a.s[k - i + 1];
if ( tem % b == i) {
a.s[k] = i;
Find (tem / b, k + 1);
}
}
}
int main() {
cin >> b >> n;
for (int i = 0; i < b; i++) {
if (i * i % b == i) {
a.s[1] = i;
Find (i * i / b, 2);
}
}
sort (ans.begin(), ans.end() );
cout << (int) ans.size() << endl;
for (int i = 0; i < (int) ans.size(); i++) {
for (int j = n; j > 0; j--)
if (ans[i].s[j] <= 9)
putchar (char ('0' + ans[i].s[j]) );
else putchar ('A' + ans[i].s[j] - 10);
cout << endl;
}
return 0;
}