浪费资源
改整体搜索了
#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>
mpz_t t;
unsigned int d = {1, 4, 9}, maxlvl;
mpz_t l;
int check(int lvl, mpz_t n)
{
// gmp_printf("%Zd\n", n);
if (mpz_perfect_square_p(n))
{
mpz_sqrt(t, n);
gmp_printf("%u: [%Zd, %Zd]\n", lvl, n, t);
}
}
int circle(int lvl)
{
if (lvl < maxlvl)
for (int i = 0; i < 3; i ++ )
{
mpz_mul_ui(l, l, 10);
mpz_add_ui(l, l, d);
check(lvl+1, l);
circle(lvl + 1);
}
}
int main(void)
{
int i;
mpz_init(t);
for (i = 0; i < 32; i ++)
{
mpz_init(l);
mpz_set_ui(l, 0);
}
printf("请输入最大数字长度：");
scanf("%u", &maxlvl);
for (i = 0; i < 3; i ++)
{
mpz_set_ui(l, d);
circle(1);
}
for (i = 0; i < 32; i ++)
mpz_clear(l);
mpz_clear(t);
return 0;
}
构造法求解
原帖由 medie2005 于 2009-3-24 14:17 发表 http://bbs.emath.ac.cn/images/common/back.gif谁来解Q4?
注意到：
1002020012 = 10040441004404001
100020200012 = 100040404100404040001
10000202000012 = 1000040400410040040400001
。。。
在100202001中“202”的两侧同时添上相同数目的“0”，其平方可仅由0、1、4构成，
（这是我刚刚通过 HugeCalc 发现的，不知是否已有人总结出来了？）
但上面最大的遗憾是其底数肯定为合数（因为其数字和=6，必被3整除）！:'(
怎么办呢？:Q:
我继续使用 HugeCalc 去 try，又发现了一个类似的规律：
1002220012 = 10044449484444001
100022200012 = 100044404948404440001
10000222000012 = 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=222，:)
这样可将右侧看作是：4*(k-2)个“0”、2个“1”、7个“4”、1个“9”和1个“484”构成。
且现在底数将有可能为素数了。于是赶紧编程进行搜索。
代码如下：#include <stdio.h>
#include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
#include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h" // 10进制系统
#pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
int main(int argc, char* argv[])
{
// 初始化
HugeCalc::EnableTimer( TRUE );
HugeCalc::ResetTimer();
// 100 222 001
CHugeInt hHead( 100000000 );
CHugeInt hMid( 222000 );
CHugeInt hSum;
UINT32 k = 3;
do
{
++(( hSum = hHead ) += hMid );
if ( hSum.IsPrime() )
{
printf( "\n%s\tk=%u\t", HugeCalc::GetTimerStr( FT_DOT06SEC_s ), k );
printf( "%s ^ 2 = ", (LPCTSTR)hSum );
printf( "%s", (LPCTSTR)hSum.Pow(2) );
}
hHead.DecLShift(2);
hMid.DecLShift(1);
} while ( ++k <= 1024 );
printf( "\n" );
HugeCalc::EnableTimer( FALSE );
system( "pause" );
return 0;
}在 k <= 1024 范围内搜索其底数恰好为素数者，结果如下：0.000183 s k=4
0.047009 s k=98
2.671768 s k=300
19.800347 s k=498
124.983792 s k=788
187.051473 s k=860
请按任意键继续. . .其中当 k=98 时，
1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000022200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 ^ 2 = 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000044400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000494840000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000044400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
可以看作 Q4 的一个解。:) :)
所以他限定不能有0
否则平凡解太多了啊 刚去尝试暴力找28位以下的
后来一算
需要的时间忒多了点
（恐怕要几十年）
只好先找24位以下的了
这个也估计要几个小时到几天吧
回复 13# 无心人 的帖子
我没见他有如此限制。当要求为素数的完全平方数，即便含上“0”也是凤毛麟角啊。 :)
不是吧
有0的很多吧
07^2 = 0049
007^2 = 000049
...
...
哈哈 3:
5:
7:
7:
7:
5:
7:
7: //素数
5: //素数
7:
8:
8:
8:
3:
5:
7:
4:
6:
8:
5:
7:
7:
8:
3:
5:
7:
7:
5:
7:
8:
6:
8:
3:
5:
7:
5:
7:
2:
4:
6:
8:
8: //素数
6: //素数
8:
8:
3:
5:
7:
6:
8:
4: //素数
6:
8:
8:
7:
6: //素数
8:
7:
8:
如果不限制0
其中素数是6个 原帖由 无心人 于 2009-3-24 16:08 发表 http://bbs.emath.ac.cn/images/common/back.gif
:)
不是吧
有0的很多吧
07^2 = 0049
007^2 = 000049
...
...
哈哈
但 0049 和 000049 它们代表的是同一个数，
应该不能算作不同的解。
所以即便加上“0”（其实它本身就是合法的，只是再肯定一下而已），
也不致于让问题难度退化到一般情形。 不玩了
暴力穷举太消耗时间了 1，4，9的留给有能力的去算吧
我只得到19位以下无比Q3大的了
响应郭老大的建议，我算下0, 1, 4, 9的16位以内的结果