正整数A×颠倒数(A)=正整数B×颠倒数(B)

l4m2

目前程序。无心说逆序函数有得优化。

1. #include <stdio.h>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. #include <omp.h>
   
5. #include <mutex>
   
6. 
   
7. typedef unsigned int hword;
   
8. typedef int shword;
   
9. typedef unsigned long long word;
   
10. typedef __uint128_t dword;
    
11. 
    
12. constexpr word pow10(int n) {
    
13.         return n?10*pow10(n-1):1;
    
14. }
    
15. 
    
16. const int N = 13;
    
17. const hword HALFLENU = pow10((1+N)/2);
    
18. const hword HALFLEND = pow10(N/2);
    
19. 
    
20. template<int i>
    
21. word Reverse(word x, word y = 0) {
    
22.         return Reverse<i-1>(x/10, y*10+x%10);}
    
23. template<>
    
24. word Reverse<0>(word x, word y) {
    
25.         return y;}
    
26. 
    
27. template<class T>
    
28. T exgcd(T a, T b, T& x, T& y) {
    
29.         if (b == 0) {
    
30.                 x = 1, y = 0;
    
31.                 return a; }
    
32.         T g = exgcd(b, a%b, y, x);
    
33.         y -= a / b * x;
    
34.         return g; }
    
35. 
    
36. struct COutput {
    
37.         word x;
    
38.         dword y;
    
39.         COutput(word x, dword y): x(x), y(y) {}
    
40.         COutput(): x(0), y(0) {}
    
41.         bool operator< (const COutput& o) const {
    
42.                 return y < o.y; }
    
43. };
    
44. 
    
45. void Output(word* buf, int n) {
    
46.         std::sort (buf, buf+n);
    
47.         static std::mutex mu;
    
48.         std::lock_guard<std::mutex> lk(mu);
    
49.         {for (int i=0; i<n; ++i) {
    
50.                 printf ("%llu ", buf[i]); }
    
51.         putchar('\n');}
    
52. }
    
53. 
    
54. std::vector<COutput> scan(hword bottom) {
    
55.         std::vector<COutput> Ret;
    
56.         for (hword i=1; i<HALFLEND; ++i) if(i%10) {
    
57.                 shword x, y;
    
58.                 hword g = exgcd((shword)i, (shword)HALFLEND, x, y);
    
59.                 if (bottom % g) continue; // if (i==24221) fprintf(stderr, "%d!%d\n", x,g);
    
60.                 // ix=g (mod HALFLEN)
    
61.                 shword step = HALFLEND / g;
    
62.                 x %= step; //if (i==24221 || i==23331 || i==42412 || i==26304) fprintf(stderr, "%d!%d\n", x,g);
    
63.                 if (x<0) x += step;
    
64.                 word Ri = Reverse<(1+N)/2>(i) * HALFLEND;
    
65.                 hword j = (word)x * (bottom/g) % step;
    
66.                 // while (j<i) j += step;
    
67.                 j += (i-j+step-1)/step*step;
    
68.                 for (; j<HALFLEND; j+=step) if(j%10)
    
69.                 for (hword mid = 0; mid < HALFLENU; mid += HALFLEND) {
    
70.                         word Rj = Reverse<N/2>(j) * HALFLENU;
    
71.                         word RiFj = Ri + j + mid;
    
72.                         word RjFi = Rj + i + mid; //if (i==2693) fprintf(stderr, "%d!%d!%lld %lld!%.8e**%d\n", j, i, RiFj, RjFi, (double)RiFj * RjFi, step);
    
73.                         Ret.emplace_back(RiFj, (dword)RiFj * RjFi);
    
74.                 }
    
75.         }
    
76.         std::sort(Ret.begin(), Ret.end());
    
77.         Ret.emplace_back();
    
78.         dword last = 0;
    
79.         word buffer[256];
    
80.         int curN = 0;
    
81.         for (COutput& p: Ret) {
    
82.                 if (p.y != last) {
    
83.                         if (curN > 1) {
    
84.                                 Output(buffer, curN); }
    
85.                         curN = 0;
    
86.                         last = p.y;
    
87.                 }
    
88.                 buffer[curN++] = p.x; }
    
89.         return Ret;
    
90. }
    
91. 
    
92. int cnt = 0;
    
93. int main() {
    
94.         omp_set_num_threads(10);
    
95.         #pragma omp parallel for schedule(guided)
    
96.         for (int i=0; i<HALFLEND; i+=10) {
    
97.                 fprintf(stderr, "%d\r", ++cnt);
    
98.                 scan(i); }
    
99. }

复制代码

l4m2

13位所有积为偶数，重复次数大于等于5的：

1. 1112533862562 1222553693142 1223663771142 2015327734641 2214625952331 2216636831331 2435842751121
   
2. 1012504842562 1113642951142 1212560684122 2013712863331 2017336821331 2415932461111
   
3. 1203615853452 1213453692252 1323843852132 2106327743541 2123543961441 2316726741231 2335662670131
   
4. 1005047557542 1104437936322 1202755853502 2218458633111 2415947532201 2437844713101
   
5. 1104122534652 1202412374532 1212230665332 2104221655431 2121403664331 2144734410231 2310252655221
   
6. 1023328348332 1114425827412 1125547606212 2124518636211 2313644924301 2336734704201
   
7. 1224336916302 2014607547321 2215844705211 2217058544211 2412663923301 2438518332201
   
8. 1323603638532 1334306449332 1336826305332 1441431855612 1455831614412 2316306367431 2522505747321 2547705325221
   
9. 1031526367132 1114342935412 2107154654311 2141538436111 2313472833301
   
10. 1132364913232 1141517654032 1233164923312 2150537723221 2365352812111
    
11. 1215508337442 1323713827422 1334417529222 1441551853602 2427707335221 2643823715211
    
12. 1031544765552 1132546577232 1233366747312 2116355765421 2133636855321 2323574854311 2346763733211
    
13. 1105237465452 1203626557332 1214437476132 1215638544132 1322547637212 1323855625212 2106346475331
    
14. 1203506544132 1310643625212 1323723624012 2106136452231 2316516342021 2522734414011
    
15. 1022517637542 1113542946522 1124655914322 1132537468122 1233356827302 2017155665421 2051563774221
    
16. 1105346774772 1203745597452 1215758772252 1323746796132 2106554795541 2127577851441 2316556893231
    
17. 1121448536762 1233468923342 1243438873142 1343268934322 1477446741302 2252458942331 2477454841121
    
18. 1105319447442 1203715837422 1215728715222 1323953823402 2207329555221 2403827735211 2427817524111 2643943713201
    
19. 1041656877762 1143648798342 2052676788531 2217476887521 2478776825211
    
20. 1224428818302 2018048466321 2215609736211 2219629334211 2436924804201
    
21. 1030412445552 1122140556432 1222034374512 2114032655421 2302225473411
    
22. 1105347866652 1203746786532 2106556876431 2125649864331 2144776872231 2314876855221
    
23. 1105214535972 1203601586652 1321430797332 2106302776641 2312503895331
    
24. 1031354663562 1133346584142 1224337835322 1225449533322 1346635732302 2412665734311 2456447514111
    
25. 1346303077452 1467602317332 2356030385541 2568304055331 2774501526321
    
26. 1021342562352 2114416633221 2116336522221 2302643633211 2304734432211 2325623622111
    
27. 1031555865872 1134596962352 1344369947312 2114836778531 2327359964321 2559837652211
    
28. 1215518558652 1323724958532 1441563975612 1467747517212 2316518677431 2522736957321
    
29. 1122413556762 1222331677542 1331144586522 2033224557741 2214223776531 2411335685421
    
30. 1225453574772 1336946533452 1453346569332 2144543755851 2335452695541 2547934454331
    
31. 1214428367022 1322537717202 1335736417002 2207238464121 2403728535111 2427717334011 2643834604101
    
32. 1214414667972 1322522798652 1440254798532 2125225668951 2314414897641 2520445897431
    
33. 1105227734652 1215627841332 1335842761212 2125418843331 2127348722331 2337724832121
    
34. 1132467865872 1244458994352 1245588962352 1368766774032 1478658843312 2578658833221
    
35. 1223137451042 1321337603222 1453324711202 2445127331021 2641435502111
    
36. 1104253681572 1312815864132 1443951744012 2501946554121 2526915552021
    
37. 1104146534652 1214438641332 1224254772132 1332267625212 2102734456431 2142445851231 2356452651021
    
38. 1214518728312 1226639417112 2305619636211 2328629325111 2535925704201
    
39. 1123646976762 1223674897542 1235886963342 2035458867741 2216656986531 2238778843431
    
40. 1031426347122 1123244716302 2016054544311 2032516625211 2213452823301 2235542703201
    
41. 1105335854652 1213562785332 1215746761332 2123734874331 2127556832331
    
42. 1040513457762 1124051558742 1133140768542 1224115495722 2050423578531 2215042777521 2412227594511
    
43. 1011404523342 1101440534322 1112432722122 2015144521221 2031432641121
    
44. 1115042547852 1214304495732 1223150678532 1332036495612 2125032867531 2140513687431 2331063867321
    
45. 1022518736762 1343278827302 2031852786431 2218247963321 2439826561211
    
46. 1104239332322 2051353661021 2216047532111 2411563712201 2437406331101
    
47. 1224157572252 1310655626532 1322439625332 1334439624132 1454536813212 2142275751441 2545439423121
    
48. 1202630772132 1203722760132 2102730672231 2104603851231 2106514830231 2314830651021
    
49. 1344003875064 2352006781362 2677204812132 2892145430412 4685108421231
    
50. 1478412352704 2555020946532 2587221617232 2785223271612 4874140725321
    
51. 1224662964684 2218446845862 2415934695642 2435661995442 4068658624641
    
52. 2358556609122 2416609575612 2438753906412 4229066757321 4267819336221 4647743906211
    
53. 1324814545584 2318425454772 2524813477452 4057244545851 4418423585541 4458550572441
    
54. 1011515654484 1112554954044 2015365941342 4044545951121 4448551651011
    
55. 1112421744684 2015124635862 2221512885342 4024215964431 4466830541121
    
56. 1134357598044 2458638814302 4008547667421 4404957835311 4844964722301
    
57. 1111533682284 2013515932662 2222733971142 4026427931331 4428623840121
    
58. 2244702414762 2254821412662 4066223226741 4428201555531 4822403474421
    
59. 1121316532884 1232204892444 2031237325962 2232108862542 4002732377631
    
60. 1585442536704 2536704277452 2762523649332 2774524439232 4439232485541 4834416386331
    
61. 1102440934444 1212562670404 1222363638004 2011804645342 2212761824122
    
62. 2061944642352 2118064635642 2306616383622 4264905634221 4644570824211
    
63. 1201660946544 2102906656452 2312963925132 4019276732331 4051763961231
    
64. 1030626567264 1122373739424 1133574837024 2050744865232 2114471955522
    
65. 1203626784384 2106346872672 2306546892252 2316747781152 4439654770131
    
66. 1112444935664 1223565961424 1233455867024 2015166645752 2111844657542 2216459651432 2234374972232
    
67. 1031431646784 2116123686732 2141341788432 4034134976421 4477840523211
    
68. 1202644946664 1322775962424 1333467768024 2104628656662 2314857934242 2404958653332
    
69. 1105335973584 1214643996144 1215746892144 2125626993252 4015853795331
    
70. 1234322736804 2233512828522 2432341863702 2456640713502 4406127474411
    
71. 1124277786684 1235458988244 1358867766204 2469758845122 2677768833402
    
72. 1124247459024 2215428816312 2347438506102 4205728625211 4625834703201
    
73. 1311723518544 1324827504144 1441324827504 1455723517104 2522318448132
    
74. 1344134656704 2306424375732 2352235649232 2532253683612 2557550642412 4036242657531 4431443946321 4475713624221
    
75. 2317237489332 2523519758412 2548935517212 4416159577221 4857726516111
    
76. 1122336816444 1132427656044 1234445932404 1245544736004 2051364852342 2211663726522 2231548616322 2454455803302
    
77. 1104254785584 1213455888144 2318667852132 2547963744012 4057668741231 4458936552021
    
78. 1021517457264 1112453729424 1123555827024 2132717746122 2322573925302 2345752815102
    
79. 1441324801584 1453105571184 1584027504144 2522318402772 4450135811751
    
80. 1041648698484 1135294998444 2237198967522 4044948968421 4408597965411
    
81. 1104253584264 1213454568024 2123545494042 2402763745212 4204836554121
    
82. 1342268754044 1476346654004 2431486841342 2674365660122 4844547630221
    
83. 1022517747464 1123544859224 2035273884332 2122835758322 2332576827302
    
84. 1213431866784 2123505766872 2305323986652 2312541888552 4034316976641
    
85. 2306827742322 2534952751302 4205827744221 4209646633221 4625943723111
    
86. 1021444584384 2116547923332 2142564694032 4036438843221 4439634732111
    
87. 1032180954444 1040617558044 1144563818004 2050628717322 4040944825311
    
88. 1355334769824 2254461688752 2344632869742 2553353896722 4247244788631 4625337796521
    
89. 1103054641584 1213237680144 2123165940252 2316147840132 2547505560012 4053258720231 4458134730021
    
90. 2003726459542 2236176783022 2433468915202 4064278752121 4422859624111 4864654703101
    
91. 1132539776484 1357765972404 2051567955762 2236188964542 2459559671322
    
92. 1131355916544 1141527846144 1244365941504 1255553935104 2150556924432 2365373931312
    
93. 1121535485064 2031633952452 2122715943342 2234571861132 2334751942122 4229345731221
    
94. 1030427464284 1113155806644 1224347840604 2060545862142 2448328450302
    
95. 1223441878884 2216234878962 2232614898762 2431363999542 4044326988741
    
96. 1455723519984 1467504289584 1599723518544 2547516159972 4494231886851
    
97. 1345323995064 1467722881224 2142447722982 2337369701562 2354316991362
    
98. 1123375795584 1234467798144 2116359757752 2557955952312 4017657777531 4414968855321
    
99. 1114335558024 2025318555132 2027157543132 2227625625012 4204737435111 4624744504101
    
100. 2352004471152 2532004813332 2760133430412 4431008423331 4830233503221
     
101. 1002411914444 1102541850404 2212640933102 4008144641111 4408514250101
     
102. 1464146679624 2333751678762 2415733587852 2562256689342 4227533778741 4641464986431 4687832753331
     
103. 1584133359624 2337531443982 2545620296562 2772233379342 4649610464541
     
104. 2677670773224 4265965811562 4685923853142 4802557694532 8404475965431 8488435832331

复制代码

只有尾数2 4 8的有

mathe

使用我前面提议的模N/2分类，可以看出，2的幂满N/2的类别数目最多，所以最可能找到长的结果。也就是乘积的2幂应该接近或不小于N/2次。这也就会导致结果偏向偶数

mathe

mathe 发表于 2025-3-5 08:54
可以检验3是\(10^n\)的原根，也就是\(3^m \pmod {10^n}\)的周期达到模\(10^n\)的最大周期\(2^{n-2}5^{n-1}\ ...

试着推算了一下，发现有错误，
由于3关于模\(5^n\)的次数为\(4\times 5^{n-1}\), 3关于模\(2^n\)的次数在n=1,2为\(2^{n-1}\)在\(n\ge 3\)时次数为\(2^{n-2}\),
由此3关于模\(10^n\)的次数比较复杂，在\(n\ge 4\)时为\(2^{n-2}5^{n-1}\), 而在n=1,2,3的时候不同。
而\(10^n\)以内和它互素的数字数目为\(\varphi(10^n)=2^{n-1}5^{n-1}\), 这导致在\(n\ge 4\)时，使用\(3^x 2^a\)只能遍历一半数据而不是全部。这个是因为\(3^x\)模8只能遍历一半(1,3,而无法达到5和7）。
所以我们需要改为使用\(3^x\)和\(7\times 3^{x-1}\)。

所以为了枚举乘积为 \(m\times 2^s\pmod{10^n}\)，其中m为奇数，\(0\le s\lt n\), 我们需要遍历
\(u 2^a,v 2^b\)其中a+b=s, u,v为奇数而且\(uv\equiv m \pmod {5^n 2^{n-s}}\)

同样由于3关于模\(5^n\)周期为\(4\times 5^{n-1}\), 关于模\(2^{n-s}\)周期在\(n-s<=2\)时为\(n-s-1\),在\(n-s\ge 3\)时为\(n-s-2\)
当\(n-s=0,1\)时，只要穷举\(u=3^x \pmod {5^n 2^{n-s}}, v=m\times 3^{-x} \pmod {5^n 2^{n-s}}\)
当\(n-s=2\)时，由于3模4周期为2，3模\(5^n\)周期为\(4\times 5^n\),这会导致\(3^x\)要么同时覆盖两个模的偶数次方，要么同时覆盖奇数次方，只覆盖一半数据
       我们可以寻找一个模4是奇数次方，比如3，模5为偶数次方，比如1，那么可以找到奇数11，于是我们可以选择\(11\times 3^{x-1} , 3^x\)这两组数
当\(n-s=3\)时，由于3模8周期为2，只覆盖{1,3}两个数，还余下{5,7}两个数没有覆盖，为了覆盖模8的所有奇数，需要选择\(3^x, 5\times 3^{x-1}\)这两组数，为了避免后面模5问题，这里的5可以改为5+8=13.
    同样由于3模\(5^n\)周期为4的倍数，上面选择还会导致次数就同步问题，所以类似前面，我们将\(3^x\)改为\(3^x, 11\times 3^{x-1}\), \(13 \times 3^{x-1}\)改为\(13 \times 3^{x-1}, 21\times 3^{x-1}\).
而当\(n-s\ge 4\)时，由于3模\(2^{n-s}\)周期为\(2^{n-s-2}\),只覆盖一半奇数，类似n-s=3,需要选择 \(3^x, 13\times 3^{x-1}\)这两组数.
   同样由于3模\(5^n\)周期为4的倍数，上面选择还会导致次数模4同步问题，所以我们需要将\(3^x\)派生出4组，在它们模5相同时，结合上面分成8组，
发现可以选择\(1\times 3^{x-1},11\times 3^{x-1}, 21\times 3^{x-1}, 31\times 3^{x-1}, ..., 71\times 3^{x-1}\)这种公共模式。
上面的选择都仅选择了u,所以我们将除了需要提前计算\(3^{-1}\)还需要提前计算所有其他用到常数的数论倒数。不过由于只有有限那么几个，都可以提前算好。

最后还有一种时当模为\(5^n \times 2^n\)的时候，我们只要\(a+b\ge n\)
但是当\(a+b\gt n\)时，我们会要求\(uv \equiv m 2^{n-a-b} \pmod {5^n}\)
同样我们还需要计算2关于\(5^n\)的数论倒数，然后每次a+b增加1时，右边的m需要再乘上一个2的数论倒数。

通过上面的方案，我们可以将计算数论倒数这种比较复杂的计算限制在有限几个数字上，其余的在各循环内部，只需要计算两次模乘运算，从而计算量会相对比较小。

王守恩

类似的题目。找找感觉。

二进制数。正整数A×颠倒数(A)=正整数B×颠倒数(B)。

譬如:
8609375=2375(100101000111)×(111000101001)3625=2755(101011000011)×(110000110101)3125,
10171175=2527(100111011111)×(111110111001)4025=3059(101111110011)×(110011111101)3325,
30832795=4555(1000111001011)×(1101001110001)6769=4835(1001011100011)×(1100011101001)6377,
17218750=4750(1001010001110)×(1110001010010)7250=5510(1010110000110)×(1100001101010)6250,x
35034175=4775(1001010100111)×(1110010101001)7337=5539(1010110100011)×(1100010110101)6325,
38354311=4847(1001011101111)×(1111011101001)7913=5371(1010011111011)×(1101111100101)7141,
39795975=4959(1001101011111)×(1011111010011)6099=6525(1100101111101)×(1111101011001)8025,
20342350=5054(1001110111110)×(1011111100110)6118=6650(1100111111010)×(1111101110010)8050,x
41227615=5819(1011010111011)×(1101110101101)7085=5995(1011101101011)×(1101011011101)6877,
51672925=6575(1100110101111)×(1111010110011)7859=6775(1101001110111)×(1110111001011)7627,

得到一串数——2375, 2527, 4555, 4750x, 4775, 4847, 4959, 5054x, 5819, 6575, ......——OEIS没有这串数。

3组解的。2371610879733375,
=36861615(10001100100111011010101111)×(11110101011011100100110001)64338225,
=36915375(10001100110100100010101111)×(11110101000100101100110001)64244529,
=45955875(10101111010011101100100011)×(11000100110111001011110101)51606261,

4组解？直觉: 4,5,6,7,...应该无解。 凭什么？只有2个数码！太少了！

northwolves

部分三组解的：

{{6,2371610879733375,{36861615,36915375,45955875,51606261,64244529,64338225}},
{6,4743221759466750,{73723230,73830750,91911750,103212522,128489058,128676450}},
{6,9486443518933500,{147446460,147661500,183823500,206425044,256978116,257352900}},
{6,18972887037867000,{294892920,295323000,367647000,412850088,513956232,514705800}}}

mathe

mathe 发表于 2025-3-5 20:07
试着推算了一下，发现有错误，
由于3关于模\(5^n\)的次数为\(4\times 5^{n-1}\), 3关于模\(2^n\)的次数在 ...

54#的方案很复杂，很容易重复或漏解，特别时对于\(a+b\ge n\)的场景。
我们的目标是对于每个\(m\equiv ab\pmod {10^n}\),高效不重复的找出所有的(a,b).
记\( m\equiv m_5 \pmod {5^n}, m\equiv 2^{p_m} m_2 \pmod {2^n}\), 其中\(1\le m_c \lt 2^{n-p_m}\)而且\(m_2\)是奇数，
特别的在 \(m\equiv 0\pmod {2^n}\)时，我们写成\(p_m=n, m_2=1\)这种统一形式。
同样有\(a_5, a_2,p_a, b_5,b_2,p_b\)。
于是在\(p_m \lt n\)时，必然有\(p_m=p_a+p_b, m_5 \equiv a_5b_5\pmod {5^n}, m_2 \equiv a_2 b_2 \pmod {2^{n-p_m}}\)
但是在\(p_m = n\)时，有\(p_a+p_b\ge n, m_5 \equiv a_5 b_5\pmod {5^n}, m_2 \equiv a_2b_2 2^{p_a+p_b-n}\pmod {2^n}\).
\(m_5\)是5的倍数时，要求\(p_m\)是0，这种特殊情况比较简单而且解比较少，如果我们仅追求解数目比较多的情况，可以忽略不看。
而对于\(m_5\)不是5的倍数，我们可以写成\(m_5\equiv 3^{u_m}\pmod {5^n}\),同理有\(u_a,u_b\)
于是\(u_a+u_b \equiv u_m 4\times 5^{n-1} \).
另外穷举时，我们需要尽量避免\(m\equiv ab \pmod {10^n}\)和\(m\equiv ba\pmod{10^n}\)同时出现。
所以可以限定只搜索\(p_a\le p_b\)的情况，而对于\(p_a - p_b\)的情况，要求\(u_a\le u_b\), 通过这种方式，可以尽量降低了计算复杂度。
而由于搜索过程还需要限定\(m_2 \equiv a_2 b_2 \pmod {2^n}\),对于给定\(a_2\),我们还是需要计算\(a_2^{-1}\pmod {n-p_m}\),为了简化代码，这部分还是可以直接求模逆，但是我们需要将遍历\(a_2\)的循环作为外循环，遍历\(u_a\)的循环作为内循环，这样计算模逆的次数也不会很多，计算量比较可控

而对于每个给定的比如\(u_a, a_2,p_a\),我们最后需要重构a,计算过程，在\(u_a\)逐步加1的枚举过程，每次迭代结束时通过乘以3模\(5^n\)得到\(a_5\)
另外我们可以提前计算\(inv_2=(2^n)^{-1}\pmod{5^n}2^n\)和\(inv_5=(5^n)^{-1}\pmod{2^n}5^n\)
然后就可以通过计算\(a_5 \times inv_2+a_2 2^{p_a} \times inv_5 \pmod{10^n}\)有效的得到a.