Ten digit numbers
很有趣的问题刚写了两篇文章：Largest Ten Digit Powers
Smallest Ten Digit Powers
算得太累了,vb实在是太慢了，c++ 尚未学到家，谁能帮帮忙？或者提供相应的理论支持？
经过大家天衣无缝的协作，已得到结果，放在 119#；程序及源码在 70#
——gxqcn
OEIS对应结果，数目在A357755,最小数在A154566， 最大数在A154532 通过计算，一个10位数，如果其n次方恰好含0-9各n次，其理论出现的个数为：
(10n)!*(10^10-10^(10-1/n))/((n!)^10 * 10^((10*n)-10^(10*n-1))
我已经计算出满足条件的 n<=18 的 最小10位数 和 n<=20 的最大10位数。 其实速度同语言应该关系不是太大。VB如果编译后执行，速度应该也就比C慢上几倍。
不过如果用C,所有大数运算可以直接调用gmp库，也许可以快一些，不知道VB里面是否能够使用，倒是你可以在VB里面调用gxq的HugeCalc。
不过你的程序里面枚举所有0-9各出现一次的10位数的方法，倒是可以改善一下，直接构造这9*9!个数就可以了，不过这部分影响可能不算太大。 第一个版本
不过似乎有点慢
#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
int digitNum;
mpz_t m, t6;
void init(void)
{
int i1, i2, i3, i4, i5, i6, n;
for (i1 = 0; i1 <= 9; i1 ++)
for (i2 = 0; i2 <= 9; i2 ++)
for (i3 = 0; i3 <= 9; i3 ++)
for (i4 = 0; i4 <= 9; i4 ++)
for (i5 = 0; i5 <= 9; i5 ++)
for (i6 = 0; i6 <= 9; i6 ++)
{
n = (i1 << 16 + i1 << 15 + i1 << 10 + i1 << 9 + i1 << 7 + i1 << 5);
n += (i2 << 13 + i2 << 11 - i2 << 8 + i2 << 4);
n += (i3 << 10 - i3 << 4 - i3 << 3);
n += (i4 << 6 + i4 << 5 + i4 << 2) + (i5 << 3 + i5 << 1) + i6;
digitNum++;
digitNum++;
digitNum++;
digitNum++;
digitNum++;
digitNum++;
}
}
int test(mpz_t pow, int p)
{
unsigned tmp, i;
int d;
for (i = 0; i < 10; i ++) d = 0;
while (mpz_cmp_ui(pow, 0) == 0)
{
mpz_divmod(pow, m, pow, t6);
tmp = mpz_get_ui(m);
for (i = 0; i < 10; i ++)
d += digitNum;
}
for (i = 0; i < 10; i ++)
if (d != p) return 0;
return 1;
}
int main(void)
{
int p, b, i = 0;
mpz_t n, pow;
char start;
printf("输入方幂: ");
scanf("%d", &p);
printf("输入起始数字(最大16位): ");
scanf("%s", start);
mpz_init(pow);
mpz_init(n);
mpz_init(m);
mpz_init(t6);
mpz_set_ui(t6, 1000000);
mpz_set_str(n, start, 10);
b = 0;
printf("\n");
while (b == 0)
{
i ++;
mpz_pow_ui(pow, n, p);
if (test(pow, p) == 1)
{
gmp_printf("找到[%Zd, %Zd]\n", n, pow);
break;
}
mpz_add_ui(n, n, 1);
if (i >= 100000000)
{
i = 0;
gmp_printf("搜索到%Zd\n", n);
}
}
mpz_clear(n);
mpz_clear(pow);
mpz_clear(m);
mpz_clear(t6);
return 0;
}
搜索着19的呢
70秒一个亿 似乎， 好像， 19的不存在 可以用C++代码，类似
#include <algorithm>
using namespace std;
char b={0,1,2,3,4,5,6,7,8,9};
int get_digit()
{
int s=0,i;
for(i=0;i<10;i++){s*=10;s+=b;}
}
int r;
do{
if(b==0)continue;
r=get_digit();
mpz_init_ui(x,r);
mpz_pow_ui(y,x,n);
check(y,n);
}while(next_permutation(b,b+10));
结果好像挺多的，所以LZ估算的误差好像太大了，下面是计数,括号里面是不允许0开头的数目，括号前面包含了0开头的数:
用的是gxq的HugeCalc,附件里给出了所有的结果
Total cost 164seconds
count=887(703)
count=237(174)
count=138(94)
count=117(89)
count=118(75)
count=130(83)
count=122(73)
count=140(89)
count=168(98)
count=202(111)
count=222(92)
count=255(123)
count=304(123)
count=348(158)
count=371(142)
count=386(133)
count=471(173)
count=533(178)
count=622(188) 代码
#define MAX_N 20
integer x;
char b={0,1,2,3,4,5,6,7,8,9};
int cc,dd;
void check(integer& x,integer& y, int k)
{
LPCTSTR s=y.GetStr(FS_NORMAL);
int i;
int count;
for(i=0;i<10;i++)count=0;
for(i=0;s!='\0';i++){
if('0'<=s&&s<='9'){
int h=s-'0';
count++;
if(count>k)return;
}
}
if(count<k){
printf("");
}else{
dd++;
}
cc++;
printf("%s^%d=%s\n",x.GetStr(FS_NORMAL),k,s);
}
void test()
{
int i;
x=0;
for(i=0;i<10;i++){
x*=10;x+=b;
}
integer y(x);
for(i=2;i<=MAX_N;i++){
y*=x;
check(x,y,i);
}
}
int main(int argc, char* argv[])
{
time_t t=time(NULL);
int i;
do{
if(b==0)continue;
test();
}while(next_permutation(b,b+10));
t=time(NULL)-t;
printf("Total cost %dseconds\n",t);
for(i=2;i<=MAX_N;i++){
printf("count[%d]=%d(%d)\n",i,cc,dd);
}
return 0;
}
原帖由 mathe 于 2009-1-12 11:36 发表 http://bbs.emath.ac.cn/images/common/back.gif
结果好像挺多的，所以LZ估算的误差好像太大了，下面是计数,括号里面是不允许0开头的数目，括号前面包含了0开头的数:
用的是gxq的HugeCalc,附件里给出了所有的结果
Total cost 164seconds
count=887(703)
coun ...
似乎与我的题目不一样。
我的要求是任意十位数，其n次方结果中，0-9 10个数字正好分别出现n次。
如：
9873773268^19=7855608929517570243129124902383848671305376350326251297158422748900643175003663401660063412051329789580670429726512989648355976426934188517557270873647143849124881043569143877856149091909632
等号后的数字为190位数，0-9分别出现了19次