方幂圈问题

无心人

打算这么做
假设表项有三个部分
1、key，就是降序排列的数字
2、Value，是Key的方幂和的数字的降序排列，去掉0
3、tag，标志，预置0
想这么处理，假设当前是prev
1、如果prev.value = prev.key，则保留，prev.tag = 1，表示关键点
2、如果通过prev.value查询key表，对应的项的next.tag是0， 1，则置prev.tag = -1表示处理项
3、如果对应项next.tag是-1，则置prev.tag = 1表示关键点

输出所有关键点
即可得到所有的环和数字
但需要再处理，才能翻译成真实数字环

mathe

这个题目比回归数还是要复杂很多的。相对来说，计算所有的回归数还是不难的

无心人

1. #include <stdlib.h>
   
2. #include <stdio.h>
   
3. 
   
4. #define BLen 1024* 1024
   
5. 
   
6. int B[BLen][3];
   
7. int Temp[BLen];
   
8. int powD[10];
   
9. int N, pos;
   
10. 
    
11. void init(void)
    
12. {
    
13.   int i, j;
    
14.   for (i = 0; i < BLen; i ++)
    
15.     B[i][0] = B[i][1] = B[i][2] = 0;
    
16.   for (i = 0; i <= 9; i ++)
    
17.   {
    
18.     powD[i] = i;
    
19.     for (j = 2; j <= N; j ++) powD[i] *=  i;
    
20.   }
    
21.   pos = 0;
    
22. }
    
23. 
    
24. int circle(int n, int b, int num, int ps)
    
25. {
    
26.   int i, j, k;
    
27.   if (n == 0)
    
28.   {
    
29.     B[pos][0] = num;
    
30.         B[pos++][1] = ps;
    
31.   }
    
32.   else
    
33.   {
    
34.      for (i = 1; i <= b; i ++)
    
35.            circle(n-1, i, num*10+i, ps + powD[i]);
    
36.   }
    
37. }
    
38. 
    
39. int binsearch(int key, int low, int hi)
    
40. {
    
41.         int m;
    
42.         if (low > hi) return (-1);
    
43.         if (low == hi)
    
44.        if (key == B[low][0]) return low; else return -1;
    
45.        if (key == B[low][0]) return low;
    
46.        if (key == B[hi][0]) return hi;
    
47.        if (low + 1 == hi) return -1;
    
48.         m = (low + hi) >> 1;
    
49.         if (key == B[m][0])
    
50.                 return m;
    
51.         else
    
52.                 if (key < B[m][0])
    
53.                   return binsearch(key, low, m);
    
54.             else
    
55.                   return binsearch(key, m, hi);
    
56. }
    
57. 
    
58. int toSort(int n)
    
59. {
    
60.   int D[10];
    
61.   int i, j;
    
62.   for (i = 1; i <= 9; i ++) D[i] = 0;
    
63.   while (n > 0)
    
64.   {
    
65.         D[n % 10]++;
    
66.         n /= 10;
    
67.   }
    
68.   
    
69.   D[0] = 0;
    
70.   for (i = 9; i >= 1; i --)
    
71.         if (D[i])
    
72.       for (j = 0; j < D[i]; j++)  
    
73.           {
    
74.             D[0] *= 10;
    
75.             D[0] += i;   
    
76.       }
    
77.   
    
78.   return D[0];
    
79. }
    
80. 
    
81. void mark(int pos)
    
82. {
    
83.   int i, next, j, k;
    
84.   for (i = 0; i < pos; i ++)
    
85.         if (B[i][2] == 0)  
    
86.       if (B[i][0] == B[i][1])
    
87.           {
    
88.             B[i][2] = 1;
    
89.           }
    
90.       else
    
91.       {
    
92.         next = binsearch(B[i][1], 0, pos);
    
93.         if (next == -1)
    
94.           printf("\nError: (%d, %d)", B[i][0], B[i][1]);
    
95.         else
    
96.                   if (B[next][2] != 0)
    
97.                     B[i][2] = -1;
    
98.                   else       
    
99.               {       
    
100.                     j = 0;
     
101.                     Temp[j++] = i;
     
102.                     Temp[j++] = next;
     
103.                     B[i][2] = 2;
     
104.                     B[next][2] = 2;
     
105.                     while ((B[next][2] == 0) && (B[next][0] != B[next][1]))
     
106.                     {
     
107.                           next = binsearch(B[next][1], 0, pos);  
     
108.                           Temp[j++] = next;
     
109.                           B[next][2] = 2;
     
110.                     }
     
111.                     k = j;       
     
112.                     if ((B[next][2] == -1) || (B[next][2] == 1))
     
113.                           for (j = 0; j < k; j ++) B[Temp[j]][2] = -1;
     
114.                     else
     
115.                     {
     
116.                       for (j = 0; j < k - 1; j ++)
     
117.                         B[Temp[j]][2] = -1;
     
118.                       B[next][2] = 1;
     
119.                     }
     
120.               }
     
121.       }
     
122. }
     
123. 
     
124. int main(void)
     
125. {
     
126.   int i;
     
127.   printf("Input N: ");
     
128.   scanf("%d", &N);
     
129.   init();
     
130.   for (i = 1; i <= N + 1; i ++)
     
131.     circle(i, 9, 0, 0);
     
132. 
     
133.   for (i = 0; i < pos; i ++)
     
134.           B[i][1] = toSort(B[i][1]);
     
135.   
     
136.   mark(pos);
     
137.   for (i = 0; i < pos; i ++)
     
138.           if (B[i][2] == 1)
     
139.             printf("(%d, %d)\n", B[i][0], B[i][1]);
     
140. //  printf("\n");
     
141. //  for (i = 0; i < pos; i ++)
     
142. //    printf("(%d: %d, %d, %d)", i, B[i][0], B[i][1], B[i][2]);
     
143. 
     
144. //  printf("\n%d\n", pos);
     
145. }

复制代码

=====================
输入N 范围[2..8]
输出对应的环的起始数字的数字降序排列形式
未写恢复自然形式数字的代码

无心人

N = 2的输出
(1, 1)
  1 -> 1
(4, 61)
  4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4
(9, 81)
  9 -> 81 -> 65 -> 61 -> 37
(52, 92) -> 4
(62, 4) -> 4
(63, 54) -> 4
(64, 52) -> 4
(71, 5)  -> 4
(72, 53) -> 4
(73, 85) -> 4
(81, 65) -> 4
(85, 98) -> 4
(86, 1) -> 1
(94, 97) -> 1
(98, 541)  -> 4
(311, 11)  -> 4
(621, 41) -> 4
(711, 51) -> 4
(821, 96) -> 4
(921, 86) -> 1
(941, 98) -> 4
==================
还是存在多余的行

无心人

手工分析N=2 仅有一个环
4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4

无心人

1. 
   
2. #include <stdlib.h>
   
3. #include <stdio.h>
   
4. 
   
5. #define BLen 1024* 1024
   
6. 
   
7. int B[BLen][3];
   
8. int Temp[BLen];
   
9. int powD[10];
   
10. int N, pos;
    
11. 
    
12. void init(void)
    
13. {
    
14.   int i, j;
    
15.   for (i = 0; i < BLen; i ++)
    
16.     B[i][0] = B[i][1] = B[i][2] = 0;
    
17.   for (i = 0; i <= 9; i ++)
    
18.   {
    
19.     powD[i] = i;
    
20.     for (j = 2; j <= N; j ++) powD[i] *=  i;
    
21.   }
    
22.   pos = 0;
    
23. }
    
24. 
    
25. int circle(int n, int b, int num, int ps)
    
26. {
    
27.   int i, j, k;
    
28.   if (n == 0)
    
29.   {
    
30.     B[pos][0] = num;
    
31.         B[pos++][1] = ps;
    
32.   }
    
33.   else
    
34.   {
    
35.      for (i = 1; i <= b; i ++)
    
36.            circle(n-1, i, num*10+i, ps + powD[i]);
    
37.   }
    
38. }
    
39. 
    
40. int binsearch(int key, int low, int hi)
    
41. {
    
42.         int m;
    
43.         if (low > hi) return (-1);
    
44.         if (low == hi)
    
45.        if (key == B[low][0]) return low; else return -1;
    
46.        if (key == B[low][0]) return low;
    
47.        if (key == B[hi][0]) return hi;
    
48.        if (low + 1 == hi) return -1;
    
49.         m = (low + hi) >> 1;
    
50.         if (key == B[m][0])
    
51.                 return m;
    
52.         else
    
53.                 if (key < B[m][0])
    
54.                   return binsearch(key, low, m);
    
55.             else
    
56.                   return binsearch(key, m, hi);
    
57. }
    
58. 
    
59. int toSort(int n)
    
60. {
    
61.   int D[10];
    
62.   int i, j;
    
63.   for (i = 1; i <= 9; i ++) D[i] = 0;
    
64.   while (n > 0)
    
65.   {
    
66.         D[n % 10]++;
    
67.         n /= 10;
    
68.   }
    
69.   
    
70.   D[0] = 0;
    
71.   for (i = 9; i >= 1; i --)
    
72.         if (D[i])
    
73.       for (j = 0; j < D[i]; j++)  
    
74.           {
    
75.             D[0] *= 10;
    
76.             D[0] += i;   
    
77.       }
    
78.   
    
79.   return D[0];
    
80. }
    
81. 
    
82. void mark(int pos)
    
83. {
    
84.   int i, next, j, k;
    
85.   for (i = 0; i < pos; i ++)
    
86.     if (B[i][0] == B[i][1])
    
87.       B[i][2] = 1;
    
88.     else
    
89.         if (B[i][2] == 0)  
    
90.       {
    
91.         next = binsearch(B[i][1], 0, pos-1);
    
92.                 if (B[next][2] != 0)
    
93.                   B[i][2] = -1;
    
94.                 else       
    
95.             {       
    
96.                   j = 0;
    
97.                   Temp[j++] = i;
    
98.                   Temp[j++] = next;
    
99.                   B[i][2] = 2;
    
100.                   while (B[next][2] == 0)
     
101.                   {
     
102.                    B[next][2] = 2;
     
103.                    next = binsearch(B[next][1], 0, pos-1);  
     
104.                    Temp[j++] = next;
     
105.                   }
     
106.                   k = j;       
     
107.                   if ((B[next][2] == -1) || (B[next][2] == 1))
     
108.                    for (j = 0; j < k - 1; j ++) B[Temp[j]][2] = -1;
     
109.                   else
     
110.               {
     
111.                     for (j = 0; j < k - 1; j ++)
     
112.                       B[Temp[j]][2] = -1;
     
113.                     B[next][2] = 1;
     
114.                   }
     
115.             }
     
116.       }
     
117. }
     
118. 
     
119. int powerDigit(int n)
     
120. {
     
121.    int r = 0, k = n;
     
122.    while (k > 0)
     
123.    {
     
124.        r += powD[k % 10];
     
125.        k /= 10;
     
126.    }
     
127.    return r;
     
128. }
     
129. 
     
130. void write(int n)
     
131. {
     
132.   int first, next;
     
133.   first = powerDigit(n);
     
134.   printf("%d -> ", first);
     
135.   next = first;
     
136.   next = powerDigit(first);
     
137.   while (next != first)
     
138.   {
     
139.     printf("%d -> ", next);
     
140.     next = powerDigit(next);
     
141.   }
     
142.   printf("%d\n", next);   
     
143. }
     
144. 
     
145. int main(void)
     
146. {
     
147.   int i;
     
148.   printf("Input N: ");
     
149.   scanf("%d", &N);
     
150.   init();
     
151.   for (i = 1; i <= N + 1; i ++)
     
152.     circle(i, 9, 0, 0);
     
153. 
     
154.   for (i = 0; i < pos; i ++)
     
155.           B[i][1] = toSort(B[i][1]);
     
156. 
     
157.   mark(pos);
     
158.   
     
159. //  for (i = 0; i < pos; i ++) printf("(%d, %d, %d) ", B[i][0], B[i][1], B[i][2]);
     
160.   printf("\n");
     
161.   
     
162.   for (i = 0; i < pos; i ++)
     
163.           if (B[i][2] == 1)
     
164.       {
     
165.             printf("(%d, %d)\n        ", B[i][0], B[i][1]);
     
166.         write(B[i][1]);
     
167.       }
     
168.    return 0;      
     
169. }
     

复制代码

终于正确了，都是瞬间完成
增加了输出
N > 8的只要修改使用大数运算和有足够的缓存，也是能求出的

无心人

N = 2
(1, 1)
        1 -> 1
(2, 4)
        16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16
==============================================
N = 3
(1, 1)
        1 -> 1
(52, 331)
        55 -> 250 -> 133 -> 55
(61, 721)
        352 -> 160 -> 217 -> 352
(73, 73)
        370 -> 370
(74, 74)
        407 -> 407
(442, 631)
        244 -> 136 -> 244
(531, 531)
        153 -> 153
(731, 731)
        371 -> 371
(991, 9541)
        919 -> 1459 -> 919
=======================================
N = 4
(1, 1)
        1 -> 1
(882, 882)
        8208 -> 8208
(6431, 6431)
        1634 -> 1634
(8721, 6541)
        2178 -> 6514 -> 2178
(9744, 9744)
        9474 -> 9474
(9921, 93311)
        6725 -> 4338 -> 4514 -> 1138 -> 4179 -> 9219 -> 13139 -> 6725

无心人

N = 5
(1, 1)
        1 -> 1
(541, 541)
        4150 -> 4150
(652, 9331)
        59536 -> 73318 -> 50062 -> 10933 -> 59536
(761, 85442)
        37973 -> 93149 -> 119366 -> 74846 -> 59399 -> 180515 -> 39020 -> 59324 -> 63473 -> 26093 -> 67100 -> 24584 -> 37973
(5411, 5411)
        4151 -> 4151
(9761, 86333)
        41273 -> 18107 -> 49577 -> 96812 -> 99626 -> 133682 -> 41063 -> 9044 ->
61097 -> 83633 -> 41273
(9842, 98732)
        108899 -> 183635 -> 44156 -> 12950 -> 62207 -> 24647 -> 26663 -> 23603 -> 8294 -> 92873 -> 108899
(9843, 9843)
        93084 -> 93084
(64311, 954)
        63198 -> 99837 -> 167916 -> 91410 -> 60075 -> 27708 -> 66414 -> 17601 ->  24585 -> 40074 -> 18855 -> 71787 -> 83190 -> 92061 -> 66858 -> 84213 -> 34068 -> 41811 -> 33795 -> 79467 -> 101463 -> 9045 -> 63198
(86533, 55441)
        8299 -> 150898 -> 127711 -> 33649 -> 68335 -> 44155 -> 8299
(87544, 87544)
        54748 -> 54748
(88651, 87643)
        58618 -> 76438 -> 58618
(96532, 7522)
        19996 -> 184924 -> 93898 -> 183877 -> 99394 -> 178414 -> 51625 -> 14059-> 63199 -> 126118 -> 40579 -> 80005 -> 35893 -> 95428 ->   95998 -> 213040 -> 1300 -> 244 -> 2080 -> 32800 -> 33043 -> 1753 -> 20176 -> 24616 -> 16609 -> 74602 -> 25639 -> 70225 -> 19996
(97722, 97722)
        92727 -> 92727
(98883, 976551)
        89883 -> 157596 -> 89883
(999741, 999741)
        194979 -> 194979

无心人

N = 6
(1, 1)
        1 -> 1
(6555, 95331)
        548525 -> 313179 -> 650550 -> 93531 -> 548525
(8643, 653321)
        63804 -> 313625 -> 63804
(8741, 98833)
        1057187 -> 513069 -> 594452 -> 570947 -> 786460 -> 477201 -> 239459 -> 1083396 -> 841700 -> 383890 -> 1057187
(85431, 985522)
        824963 -> 845130 -> 282595 -> 824963
(776541, 76631)
        211691 -> 578164 -> 446171 -> 172499 -> 1184692 -> 844403 -> 275161 -> 179996 -> 1758629 -> 973580 -> 927588 -> 1189067 -> 957892 -> 1458364 -> 333347 -> 124661 -> 97474 -> 774931 -> 771565 -> 313205 -> 17148 -> 383891 -> 1057188 -> 657564 -> 246307 -> 169194 -> 1113636 -> 94773 -> 771564 -> 301676 -> 211691
(885443, 885443)
        548834 -> 548834

无心人

N = 7
(1, 1)
        1 -> 1
(98763, 9887775)
        11526027 -> 1181862 -> 4474371 -> 1698426 -> 7456506 -> 1556049 -> 5235540 -> 253074 -> 920367 -> 5888763 -> 7475247 -> 2581650 -> 2533467 -> 1202490 -> 4799610 -> 10685802 -> 4552494 -> 4988499 -> 18575979 -> 13466427 -> 1418499 -> 11695860 -> 7518120 -> 2998950 -> 16524312 -> 376890 -> 7985787 -> 11526027
(98821, 987742)
        8543719 -> 7800361 -> 3202819 -> 6882565 -> 4910554 -> 4971988 -> 14600170 -> 1119865 -> 7238185 -> 5098288 -> 11152678 -> 3278887 -> 7940857 -> 8621716 -> 3480697 -> 8002171 -> 2920825 -> 6958630 -> 7520305 -> 982108 -> 8977402 -> 8543719
(98871, 98871)
        9800817 -> 9800817
(884211, 884211)
        4210818 -> 4210818
(965531, 5433221)
        99140 -> 9582323 -> 6962876 -> 8543600 -> 2473784 -> 3779321 -> 6434558 -> 2568293 -> 7240625 -> 1198244 -> 6913019 -> 9848063 -> 9275780 -> 8605460 -> 2751533 -> 984296 -> 11959538 -> 11821529 -> 6958505 -> 7394432 -> 5643782 -> 3297455 -> 5781461 -> 3295142 -> 4879922 -> 12503273 -> 906299 -> 14628971 -> 8000114 -> 2113538 -> 2179781 -> 8527337 -> 3826865 -> 4834616 -> 2691980 -> 11943155 -> 4957793 -> 11309720 -> 5608829 -> 9335462 -> 5161916 -> 5420969 -> 9940511-> 9660449 -> 10158578 -> 5174099 -> 10483991 -> 11681663 -> 2939150 -> 9646379 -> 10967924 -> 10685930 -> 7240370 -> 1665785 -> 3636818 -> 4758551 -> 3171455 -> 998366 -> 12225149 -> 4877864 -> 6154094 -> 5173799 -> 11293337 -> 5613203 -> 362564 -> 656696 -> 5980838 -> 11154737 -> 1743785 -> 3840935 -> 6979004 -> 10685801 -> 4552367 -> 1278428 -> 5034488 -> 4307384 -> 2957837 -> 8607647 -> 4320494 -> 4834436 -> 2430614 -> 315020 -> 80441 -> 2129921 -> 9566324 -> 5439665 -> 5517662 -> 1539794 -> 10486178 -> 5314169 -> 5159603 -> 5221343 -> 99140
(976432, 975541)
        5779147 -> 7348108 -> 5036419 -> 5159602 -> 5219284 -> 6974887 -> 10920679 -> 10669546 -> 5717287 -> 4646035 -> 672952 -> 5964829 -> 12037663 -> 1387918 -> 9803005 -> 6960433 -> 5363599 -> 10006498 -> 7176442 -> 1959919 -> 19210003-> 4785286 -> 5392420 -> 4879921 -> 12503146 -> 376762 -> 2209273 -> 5609083 ->7240369 -> 5905147 -> 5779147
(977552, 8665433)
        2755907 -> 6586433 -> 2755907
(984222, 9988866)
        16417266 -> 1679865 -> 8341662 -> 2675724 -> 2021787 -> 3744495 -> 5735976 -> 6868428 -> 6867840 -> 5594103 -> 4957791 -> 11307534 -> 922428 -> 6896889-> 16417266
(988531, 987655)
        8139850 -> 9057586 -> 8139850
(7433211, 844431)
        2148492 -> 6913146 -> 5361414 -> 393018 -> 6884496 -> 9569913 -> 14709156 -> 5980959 -> 16602309 -> 5345157 -> 1076490 -> 5902833 -> 6962748 -> 8280048-> 6307968 -> 8265723 -> 3281199 -> 11665407 -> 1477926 -> 6726504 -> 1478052 -> 3015333 -> 86874 -> 5314167 -> 1200177 -> 1647216 -> 1399929 -> 19134192 -> 9584640 -> 7270950 -> 6508308 -> 4554552 -> 345396 -> 5161788 -> 5375910 -> 5764950 -> 6059082 -> 7238310 -> 2925198 -> 11741472 -> 1679985 -> 12844695 -> 7271079-> 7253727 -> 2551197 -> 5762892 -> 8061981 -> 9257211 -> 5684895 -> 9429843 ->11698173 -> 7985790 -> 13388301 -> 4200867 -> 3217143 -> 844431 -> 2148492
(7754211, 7754211)
        1741725 -> 1741725
(9663211, 8555431)
        2350099 -> 9646378 -> 8282107 -> 5018104 -> 2191663 -> 5345158 -> 2350099
(9766421, 9887621)
        10080881 -> 6291458 -> 7254695 -> 6059210 -> 5141159 -> 4955606 -> 5515475 -> 1152428 -> 2191919 -> 14349038 -> 6917264 -> 6182897 -> 10080881
(9877621, 887722)
        5841646 -> 2767918 -> 8807272 -> 5841646
(9965321, 9965321)
        9926315 -> 9926315
(99954421, 99954421)
        14459929 -> 14459929