上面的公式有个问题，没有考虑到对于越大的数，对应的计算量越大。由于我们实际计算过程都是一个超大整数乘上一个小于\(10^{10}\)的整数
所以实际上每次乘法本身就是O(n)的，由此总体复杂度可以表示为
\(\sum_{x=10^9}^{10^{10}-1}\frac{x\ln(0.1)}{\ln(10^{-10}x)}\approx 10^{20}\ln(0.1)(Ei(2\ln(1-10^{-10}))-Ei(2\ln(0.1)))\).
而计算过程中，如果我们从\(10^9\)已经计算到\(10^{10}-10^7\),那么我们就可以估算出计算过程已经占了整体计算量的
\(\frac{Ei(2\ln(0.999))-Ei(2\ln(0.1)))}{Ei(2\ln(1-10^{-10}))-Ei(2\ln(0.1)))} \approx 0.2088\)
通过这种方法可以估算出完成整个计算大概需要8K CPU日左右, 对于现代多核处理器也不是不能完成，就是时间略微长了点，如果能够优化一下会更好。
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <time.h>
#define SN 501
#define MP 100000000
#define MOD 10000000000L
#define HMOD 100000
char dc;
void initdc()
{
int i;
for(i=0;i<HMOD;i++){
int j;
int x=i;
for(j=0;j<5;j++){
dc++;
x/=10;
}
}
}
void get_count(long v[],int length, int count)
{
int i;
for(i=0;i<10;i++)count=0;
for(i=0;i<length;i++){
int x=v%HMOD;
int y=v/HMOD;
int j;
for(j=0;j<10;j++){
count+=dc+dc;
}
}
}
bool mulby(long v[], int length, long m)
{
int i;
long carry=0L;
for(i=0;i<length;i++){
__int128_t prod = (__int128_t)v*m+carry;
v=prod%MOD;
carry=prod/MOD;
}
v=carry;
return carry>=(MOD/10);
}
int main()
{
double sv=pow(0.1,1.0/SN)*MOD;
long is = (long)ceil(sv);
initdc();
time_t start=time(NULL);
#pragma omp parallel
{
long *data = (long *)malloc((MP+1)*sizeof(long));
#pragma omp for schedule(dynamic)
for(long i=is;i<MOD;i++){
int count;
data=i;
int j;
for(j=2;j<=MP;j++){
if(!mulby(data,j-1,i))break;
if(j<SN)continue;
get_count(data,j,count);
int k;
for(k=0;k<10;k++)if(count!=j)break;
if(k==10){
#pragma omp critical
{
printf("%ld^%d\n",i,j);
fflush(stdout);
}
}
}
#pragma omp critical
if(i%1000000==0)
{
time_t now=time(NULL);
fprintf(stderr,"%ld cost %ld\n",i,now-start);
fflush(stderr);
}
}
}
printf("done!\n");
return 0;
}
小心翼翼的问。
一个10位数, 其n次方恰好含0-9各n次。——这是主帖。
一个9位数, 其n次方恰好含0-9各n次。——会有吗？
一个8位数, 其n次方恰好含0-9各n次。——会有吗？
一个7位数, 其n次方恰好含0-9各n次。——会有吗？
一个10位数, 其n次方恰好含0-9各n次。——这是主帖。
一个11位数, 其n次方恰好含0-9各n次。——会有吗？
一个12位数, 其n次方恰好含0-9各n次。——会有吗？
一个13位数, 其n次方恰好含0-9各n次。——会有吗？
比较让人以外的是mulby中除法编译并没有进行优化，可以手工优化一下
bool mulby(long v[], int length, long m)
{
int i;
long D=990352031428304219L;
long carry=0L;
for(i=0;i<length;i++){
__int128_t prod = (__int128_t)v*m+carry;
long val = (long)((prod*D)>>93);
long res=(long)(prod-val*(__int128_t)MOD);
if(res>=MOD){
val++;res-=MOD;
}
v=res;
carry=val;
}
v=carry;
return carry>=(MOD/10);
}
另外现在代码里面
long *data = (long *)malloc((MP+1)*sizeof(long));
需要对于比较大的MP需要分配比较大的内存，如果线程数目多的话对于内存压力很大，实际计算过程就需要对于大的MP采用较少线程数目来节省内存开销。