我们考虑，因为最多n为10^7, 7*9 = 63，也就是说一个数x如果不是self-number，那么他的原数一定在[x-63, x]之间。
由于空间有限，所以我们可以用大小>=64的数组优化（只要能存下前63个数即可）。
另外一个优化，打表处理10^4之内的每位数字之和， 则d(x) = x + sum[x/10000] + sum[x%10000];
还有一个坑点是， 查询数字的值不一定是递增的， 也可能有重复的查询。。。
1 /*Author :usedrose */ 2 /*Created Time :2015/7/24 11:09:55*/ 3 /*File Name :2.cpp*/ 4 #include <cstdio> 5 #include <iostream> 6 #include <algorithm> 7 #include <sstream> 8 #include <cstdlib> 9 #include <cstring> 10 #include <climits> 11 #include <vector> 12 #include <string> 13 #include <ctime> 14 #include <cmath> 15 #include <deque> 16 #include <queue> 17 #include <stack> 18 #include <set> 19 #include <map> 20 #define INF 0x3f3f3f3f 21 #define eps 1e-8 22 #define pi acos(-1.0) 23 #define MAXN 10110 24 #define OK cout << "ok" << endl; 25 #define o(a) cout << #a << " = " << a << endl 26 #define o1(a,b) cout << #a << " = " << a << " " << #b << " = " << b << endl 27 using namespace std; 28 typedef long long LL; 29 30 struct node { 31 int num, index, ans; 32 }a[MAXN]; 33 bool f[100]; 34 int n, m; 35 int sum[MAXN]; 36 37 bool cmp1(node a, node b) 38 { 39 return a.index < b.index; 40 } 41 42 bool cmp2(node a, node b) 43 { 44 return a.num < b. num; 45 } 46 void init() 47 { 48 for (int i = 1;i <= 10000; ++ i) 49 { 50 int k = i; 51 while (k) { 52 sum[i] += k%10; 53 k /= 10; 54 } 55 } 56 } 57 58 int main() 59 { 60 //freopen("data.in","r",stdin); 61 //freopen("data.out","w",stdout); 62 cin.tie(0); 63 ios::sync_with_stdio(false); 64 init(); 65 66 while (cin >> n >> m) { 67 for (int i = 1;i <= m; ++ i) { 68 cin >> a[i].index; 69 a[i].num = i; 70 } 71 sort(a+1, a+1+m, cmp1); 72 int di = 0, cur = 1; 73 memset(f, 1, sizeof(f)); 74 for (int i = 1;i <= n; ++ i) { 75 if (f[i%64]) { 76 di++; 77 while (a[cur].index == di && cur <= m) { 78 a[cur].ans = i; 79 cur++; 80 } 81 } 82 f[i%64] = 1; 83 int nxt = i + sum[i/10000] + sum[i%10000]; 84 f[nxt%64] = 0; 85 } 86 87 cout << di << endl; 88 sort(a+1, a+1+m, cmp2); 89 cout << a[1].ans; 90 for (int i = 2;i <= m; ++ i) 91 cout << " " << a[i].ans; 92 cout << endl; 93 } 94 return 0; 95 }