打算这么做
假设表项有三个部分
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表示关键点
输出所有关键点
即可得到所有的环和数字
但需要再处理，才能翻译成真实数字环
这个题目比回归数还是要复杂很多的。相对来说，计算所有的回归数还是不难的
#include <stdlib.h>
#include <stdio.h>
#define BLen 1024* 1024
int B;
int Temp;
int powD;
int N, pos;
void init(void)
{
int i, j;
for (i = 0; i < BLen; i ++)
B = B = B = 0;
for (i = 0; i <= 9; i ++)
{
powD = i;
for (j = 2; j <= N; j ++) powD *=i;
}
pos = 0;
}
int circle(int n, int b, int num, int ps)
{
int i, j, k;
if (n == 0)
{
B = num;
B = ps;
}
else
{
for (i = 1; i <= b; i ++)
circle(n-1, i, num*10+i, ps + powD);
}
}
int binsearch(int key, int low, int hi)
{
int m;
if (low > hi) return (-1);
if (low == hi)
if (key == B) return low; else return -1;
if (key == B) return low;
if (key == B) return hi;
if (low + 1 == hi) return -1;
m = (low + hi) >> 1;
if (key == B)
return m;
else
if (key < B)
return binsearch(key, low, m);
else
return binsearch(key, m, hi);
}
int toSort(int n)
{
int D;
int i, j;
for (i = 1; i <= 9; i ++) D = 0;
while (n > 0)
{
D++;
n /= 10;
}
D = 0;
for (i = 9; i >= 1; i --)
if (D)
for (j = 0; j < D; j++)
{
D *= 10;
D += i;
}
return D;
}
void mark(int pos)
{
int i, next, j, k;
for (i = 0; i < pos; i ++)
if (B == 0)
if (B == B)
{
B = 1;
}
else
{
next = binsearch(B, 0, pos);
if (next == -1)
printf("\nError: (%d, %d)", B, B);
else
if (B != 0)
B = -1;
else
{
j = 0;
Temp = i;
Temp = next;
B = 2;
B = 2;
while ((B == 0) && (B != B))
{
next = binsearch(B, 0, pos);
Temp = next;
B = 2;
}
k = j;
if ((B == -1) || (B == 1))
for (j = 0; j < k; j ++) B] = -1;
else
{
for (j = 0; j < k - 1; j ++)
B] = -1;
B = 1;
}
}
}
}
int main(void)
{
int i;
printf("Input N: ");
scanf("%d", &N);
init();
for (i = 1; i <= N + 1; i ++)
circle(i, 9, 0, 0);
for (i = 0; i < pos; i ++)
B = toSort(B);
mark(pos);
for (i = 0; i < pos; i ++)
if (B == 1)
printf("(%d, %d)\n", B, B);
//printf("\n");
//for (i = 0; i < pos; i ++)
// printf("(%d: %d, %d, %d)", i, B, B, B);
//printf("\n%d\n", pos);
}=====================
输入N 范围
输出对应的环的起始数字的数字降序排列形式
未写恢复自然形式数字的代码
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
#include <stdlib.h>
#include <stdio.h>
#define BLen 1024* 1024
int B;
int Temp;
int powD;
int N, pos;
void init(void)
{
int i, j;
for (i = 0; i < BLen; i ++)
B = B = B = 0;
for (i = 0; i <= 9; i ++)
{
powD = i;
for (j = 2; j <= N; j ++) powD *=i;
}
pos = 0;
}
int circle(int n, int b, int num, int ps)
{
int i, j, k;
if (n == 0)
{
B = num;
B = ps;
}
else
{
for (i = 1; i <= b; i ++)
circle(n-1, i, num*10+i, ps + powD);
}
}
int binsearch(int key, int low, int hi)
{
int m;
if (low > hi) return (-1);
if (low == hi)
if (key == B) return low; else return -1;
if (key == B) return low;
if (key == B) return hi;
if (low + 1 == hi) return -1;
m = (low + hi) >> 1;
if (key == B)
return m;
else
if (key < B)
return binsearch(key, low, m);
else
return binsearch(key, m, hi);
}
int toSort(int n)
{
int D;
int i, j;
for (i = 1; i <= 9; i ++) D = 0;
while (n > 0)
{
D++;
n /= 10;
}
D = 0;
for (i = 9; i >= 1; i --)
if (D)
for (j = 0; j < D; j++)
{
D *= 10;
D += i;
}
return D;
}
void mark(int pos)
{
int i, next, j, k;
for (i = 0; i < pos; i ++)
if (B == B)
B = 1;
else
if (B == 0)
{
next = binsearch(B, 0, pos-1);
if (B != 0)
B = -1;
else
{
j = 0;
Temp = i;
Temp = next;
B = 2;
while (B == 0)
{
B = 2;
next = binsearch(B, 0, pos-1);
Temp = next;
}
k = j;
if ((B == -1) || (B == 1))
for (j = 0; j < k - 1; j ++) B] = -1;
else
{
for (j = 0; j < k - 1; j ++)
B] = -1;
B = 1;
}
}
}
}
int powerDigit(int n)
{
int r = 0, k = n;
while (k > 0)
{
r += powD;
k /= 10;
}
return r;
}
void write(int n)
{
int first, next;
first = powerDigit(n);
printf("%d -> ", first);
next = first;
next = powerDigit(first);
while (next != first)
{
printf("%d -> ", next);
next = powerDigit(next);
}
printf("%d\n", next);
}
int main(void)
{
int i;
printf("Input N: ");
scanf("%d", &N);
init();
for (i = 1; i <= N + 1; i ++)
circle(i, 9, 0, 0);
for (i = 0; i < pos; i ++)
B = toSort(B);
mark(pos);
//for (i = 0; i < pos; i ++) printf("(%d, %d, %d) ", B, B, B);
printf("\n");
for (i = 0; i < pos; i ++)
if (B == 1)
{
printf("(%d, %d)\n ", B, B);
write(B);
}
return 0;
}
终于正确了，都是瞬间完成
增加了输出
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