题目描述-->p1900 自我数
本文转自@keambar
转载已经原作者同意
分析：
思路还是比较好给出的：
用类似筛选素数的方法筛选自我数。
但是要注意到题目限制的空间仅有4M,不够开10^7 那么大的数组.
于是进一步分析问题我们发现每一次拓展出来的数最多比原数大63！
这是由于最多不过7位数,假设每一位都是9的话,拓展出来的数才大 7*9=63.
所以我们，对拓展出来的数取模，再用数组存下来。
至于输出自我数,经过测试.
在SGU的数据里自我数的答案没有超过10^6
刚好用掉4M的空间 ⊙﹏⊙b汗
最保险的方法还是仅将需要的自我数号码存下来,
排序后用二分查找判断当前找到的数是否是需要存下的.
最后再将存下的数按照读入的顺序输出.
原作者代码↓
#include<cstdio>
int n, m, k;
bool pd[100];
int f[1000000], tol;
int Find (int x) {
for (k = 0; x != 0; x /= 10)
k += x % 10;
return k;
}
void init() {
int i, j;
tol = 0, j = 0;
for (i = 1; i <= n; i++) {
if (!pd[i % 100]) f[++tol] = i;
else
pd[i % 100] = false;
//这里用了个小技巧，大大减少取模的次数，很容易想明白
if (i % 10 == 0) j = i + Find (i);
else
j += 2;
pd[j % 100] = true;
}
}
int main() {
scanf ("%d%d", &n, &m);
init();
printf ("%d\n", tol);
for (int i = 1; i <= m; i++) {
scanf ("%d", &k);
printf ("%d ", f[k]);
}
return 0;
}
本人辣鸡代码就不放了emmm
应原作者要求:本题亦可以在SGU上找到
//不过,我没有找到链接 emm