恭候佳音
原帖由 无心人 于 2009-1-12 16:22 发表 http://bbs.emath.ac.cn/images/common/back.gif
#include
#include
#include
int test(mpz_t pow, int p)
{
unsigned tmp;
int d, i;
char t;
for (i = 0; i < 10; i ++) d = 0;
mpz_get_str(t, 10, pow);
for (i = 0 ...
n个0-9的数字和一定是9的倍数，所以满足条件的10位数一定是3的倍数，可提速2倍。
我倒是觉得可以批量一起搜索多个幂的情况，比如
#define MAX_TIMES 30
int TIMES=20;
int cc;
void check(integer& x,integer& y, int k)
{
LPCTSTR s=y.GetStr(FS_NORMAL);
int i;
int count;
int tc=0;
for(i=0;i<10;i++)count=0;
for(i=0;s!='\0';i++){
if('0'<=s&&s<='9'){
int h=s-'0';
count++;tc++;
if(count>k)return;
}
}
if(count+10*k-tc!=k)return;
cc++;
printf("%s^%d=%s\n",x.GetStr(FS_NORMAL),k,s);
fflush(stdout);
}
integer yt;
char buf1;
char buf2;
void test()
{
time_t t=time(NULL);
integer x(1);
long long u=1LL;
int i,mt;
int c=0;
for(i=0;i<10;i++){
x*=10;
u*=10LL;
}
integer y(x);
y/=10;
for(i=1;i<=MAX_TIMES;i++){
yt=y;
y*=x;
}
x--;u--;
mt=MAX_TIMES;
for(;u>0LL;x-=3,u-=3LL){
integer z(x);
for(i=2;i<=mt;i++){
z*=x;
strcpy(buf1,z.GetStrA(FS_NORMAL,NULL));
strcpy(buf2,yt.GetStrA(FS_NORMAL,NULL));
if(z<yt){mt=i-1;break;}
check(x,z,i);
}
if(i<=2)break;
c++;
if(c%100000==0){
time_t now=time(NULL);
fprintf(stderr,"%lld, times %ds\n",u,(int)(now-t));
}
}
t=time(NULL)-t;
printf("Total cost %dseconds\n",t);
}
int main(int argc, char* argv[])
{
int i;
test();
for(i=2;i<=MAX_TIMES;i++){
printf("c[%d]=%d\n",i,cc);
}
return 0;
}
mathe 的批量搜索的想法很好，可以减少总体计算总量。
下面是我写的单独搜索某个幂次的代码，局部做过一些优化，比如在统计每个数字的数量判断上：//Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
// Win32 Debug: Debug Multithreaded DLL
// Win32 Release:Multithreaded DLL
#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[])
{
UINT32 i, count = 0;
UINT32 r, digits;
UINT32 histogram[ 256 ] = { 0 };
LPCTSTR p;
CHugeInt hugePow, hugeBase( "10000000002" );// 10000000002 % 3 == 0
printf( "Call %s\n", HugeCalc::GetVer());
if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
{
printf( "\n警告：您未通过 HugeCalc.dll 的许可认证！\n" \
"\n解决方案可选下列方案之一：" \
"\n 一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
"\n 二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。\n\n" );
system( "pause" );
return (-1);
}
printf( "\nr = ");
scanf( "%u", &r );
HugeCalc::EnableTimer( TRUE );
HugeCalc::ResetTimer();
digits = r * 10;
for ( ; ; )
{
hugePow.Pow( hugeBase -= 3UL, r );
if ( digits != hugePow.GetDigits() )
break;
histogram[ '\0' ] = 1;
for ( i = '0'; i <= '9'; ++i )
histogram[ i ] = r + 1;
for ( p = hugePow; 0 != --histogram[ *p ]; ++p )
;
if ( '\0' == *p )
printf( "%s\tNo.%u\t%s\n", HugeCalc::GetTimerStr( FT_HHMMSS_ms ), ++count, (LPCTSTR)hugeBase );
}
printf( "\n****** %s ******\n", HugeCalc::GetTimerStr( FT_DOT06SEC_s ) );
system( "pause" );
return 0;
}
:lol
呵呵， 米想那么多
明天去优化下
因为感觉这个问题的幂并不很高
理论上不会超过10^8次幂
实际上可能在20以上就会有很多幂没结果了
明天看有时间么?
有时间打算用17台机器一起跑
最好1个小时算完
应该能搜索完40次幂以下的所有结果
肚子的代码很奇怪？
什么库？
原帖由 northwolves 于 2009-1-12 14:24 发表 http://bbs.emath.ac.cn/images/common/back.gif
我只算到20，当初按概率统计认为不会出现大于20 的数了。
后来发现，最小值当n=26时还找到一个值，也许不止一个。
n=21,9766102146
n=22,9863817738
n=24,9793730157
原帖由 无心人 于 2009-1-12 22:03 发表 http://bbs.emath.ac.cn/images/common/back.gif
肚子的代码很奇怪？
什么库？
锅呀:lol
:lol
呵呵
你怎么知道肚子指的是你？
哦
哎， 不要你们去算20-23的结果
和我在学校挂的20-23的程序冲突了
浪费掉了资源
这三个是唯一的么？
原帖由 无心人 于 2009-1-12 22:31 发表 http://bbs.emath.ac.cn/images/common/back.gif
:lol
呵呵
你怎么知道肚子指的是你？
哦
哎， 不要你们去算20-23的结果
和我在学校挂的20-23的程序冲突了
浪费掉了资源
这三个是唯一的么？
northwolves的序列，最大的一个。
我用的很慢的一台老机器，从大的数字开始搜索，如上面代码，同时计算2次幂到30次幂。反正这个序列应该这几天就可以被解决了，先抢先贴几个数字再说:)