p^2=a^2&b^2

无心人

不搜索单个的了 浪费资源 改整体搜索了

2. #include <gmp.h>
3. #include <stdio.h>
4. #include <stdlib.h>
6. mpz_t t;
7. unsigned int d[3] = {1, 4, 9}, maxlvl;
8. mpz_t l[32];
10. int check(int lvl, mpz_t n)
11. {
12. // gmp_printf("%Zd\n", n);
14. if (mpz_perfect_square_p(n))
15. {
16. mpz_sqrt(t, n);
17. gmp_printf("%u: [%Zd, %Zd]\n", lvl, n, t);
18. }
19. }
21. int circle(int lvl)
22. {
23. if (lvl < maxlvl)
24. for (int i = 0; i < 3; i ++ )
25. {
26. mpz_mul_ui(l[lvl], l[lvl-1], 10);
27. mpz_add_ui(l[lvl], l[lvl], d[i]);
28. check(lvl+1, l[lvl]);
29. circle(lvl + 1);
30. }
31. }
32. int main(void)
33. {
34. int i;
35. mpz_init(t);
36. for (i = 0; i < 32; i ++)
37. {
38. mpz_init(l[i]);
39. mpz_set_ui(l[i], 0);
40. }
41. printf("请输入最大数字长度：");
42. scanf("%u", &maxlvl);
43. for (i = 0; i < 3; i ++)
44. {
45. mpz_set_ui(l[0], d[i]);
46. circle(1);
47. }
49. for (i = 0; i < 32; i ++)
50. mpz_clear(l[i]);
51. mpz_clear(t);
52. return 0;
53. }

复制代码

gxqcn

原帖由 medie2005 于 2009-3-24 14:17 发表 谁来解Q4?

注意到： 100202001² = 10040441004404001 10002020001² = 100040404100404040001 1000020200001² = 1000040400410040040400001 。。。 在100202001中“202”的两侧同时添上相同数目的“0”，其平方可仅由0、1、4构成， （这是我刚刚通过 HugeCalc 发现的，不知是否已有人总结出来了？） 但上面最大的遗憾是其底数肯定为合数（因为其数字和=6，必被3整除）！ 怎么办呢？ 我继续使用 HugeCalc 去 try，又发现了一个类似的规律： 100222001² = 10044449484444001 10002220001² = 100044404948404440001 1000022200001² = 1000044400494840044400001 。。。 即：$(10^(2k+2)+222*10^k+1)^2=10^(4k+2)+444*10^(3k+2)+49484*10^(2k)+444*10^k+1$ 注意到右侧多出了一个8，虽然8不是完全平方数，但凑巧484=22²， 这样可将右侧看作是：4*(k-2)个“0”、2个“1”、7个“4”、1个“9”和1个“484”构成。 且现在底数将有可能为素数了。于是赶紧编程进行搜索。 代码如下：

1. #include <stdio.h>
3. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
4. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h" // 10进制系统
6. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
7. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
10. int main(int argc, char* argv[])
11. {
12. // 初始化
13. HugeCalc::EnableTimer( TRUE );
14. HugeCalc::ResetTimer();
16. // 100 222 001
17. CHugeInt hHead( 100000000 );
18. CHugeInt hMid( 222000 );
19. CHugeInt hSum;
21. UINT32 k = 3;
23. do
24. {
25. ++(( hSum = hHead ) += hMid );
26. if ( hSum.IsPrime() )
27. {
28. printf( "\n%s\tk=%u\t", HugeCalc::GetTimerStr( FT_DOT06SEC_s ), k );
29. printf( "%s ^ 2 = ", (LPCTSTR)hSum );
30. printf( "%s", (LPCTSTR)hSum.Pow(2) );
31. }
33. hHead.DecLShift(2);
34. hMid.DecLShift(1);
35. } while ( ++k <= 1024 );
37. printf( "\n" );
38. HugeCalc::EnableTimer( FALSE );
40. system( "pause" );
42. return 0;
43. }

复制代码

在 k <= 1024 范围内搜索其底数恰好为素数者，结果如下：

1. 0.000183 s k=4
2. 0.047009 s k=98
3. 2.671768 s k=300
4. 19.800347 s k=498
5. 124.983792 s k=788
6. 187.051473 s k=860
7. 请按任意键继续. . .

复制代码

其中当 k=98 时， 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000022200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 ^ 2 = 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000044400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000494840000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000044400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 可以看作 Q4 的一个解。

无心人

所以他限定不能有0 否则平凡解太多了啊

无心人

刚去尝试暴力找28位以下的 后来一算 需要的时间忒多了点 （恐怕要几十年） 只好先找24位以下的了 这个也估计要几个小时到几天吧

gxqcn

我没见他有如此限制。 当要求为素数的完全平方数，即便含上“0”也是凤毛麟角啊。

无心人

不是吧 有0的很多吧 07^2 = 0049 007^2 = 000049 ... ... 哈哈

无心人

3: [100, 10] 5: [10000, 100] 7: [1000000, 1000] 7: [1004004, 1002] 7: [1014049, 1007] 5: [10404, 102] 7: [1040400, 1020] 7: [1100401, 1049] //素数 5: [11449, 107] //素数 7: [1144900, 1070] 8: [11909401, 3451] 8: [14010049, 3743] 8: [14040009, 3747] 3: [144, 12] 5: [14400, 120] 7: [1440000, 1200] 4: [1444, 38] 6: [144400, 380] 8: [14440000, 3800] 5: [19044, 138] 7: [1904400, 1380] 7: [1940449, 1393] 8: [19909444, 4462] 3: [400, 20] 5: [40000, 200] 7: [4000000, 2000] 7: [4004001, 2001] 5: [40401, 201] 7: [4040100, 2010] 8: [40411449, 6357] 6: [419904, 648] 8: [41990400, 6480] 3: [441, 21] 5: [44100, 210] 7: [4410000, 2100] 5: [44944, 212] 7: [4494400, 2120] 2: [49, 7] 4: [4900, 70] 6: [490000, 700] 8: [49000000, 7000] 8: [49014001, 7001] //素数 6: [491401, 701] //素数 8: [49140100, 7010] 8: [49999041, 7071] 3: [900, 30] 5: [90000, 300] 7: [9000000, 3000] 6: [904401, 951] 8: [90440100, 9510] 4: [9409, 97] //素数 6: [940900, 970] 8: [94090000, 9700] 8: [94109401, 9701] 7: [9909904, 3148] 6: [994009, 997] //素数 8: [99400900, 9970] 7: [9941409, 3153] 8: [99940009, 9997] 如果不限制0 其中素数是6个

gxqcn

原帖由 无心人 于 2009-3-24 16:08 发表 不是吧 有0的很多吧 07^2 = 0049 007^2 = 000049 ... ... 哈哈

但 0049 和 000049 它们代表的是同一个数， 应该不能算作不同的解。 所以即便加上“0”（其实它本身就是合法的，只是再肯定一下而已）， 也不致于让问题难度退化到一般情形。

无心人

不玩了 暴力穷举太消耗时间了

无心人

1，4，9的留给有能力的去算吧 我只得到19位以下无比Q3大的了 响应郭老大的建议，我算下0, 1, 4, 9的16位以内的结果