我碰到了这个问题，如果数字的总和以及数字平方的和为质数，则称为幸运数字。A和B之间有多少个数字是幸运的？1 <= A <= B <= 10 18。我试过了
首先，我生成了介于1和通过平方和得出的数字之间的所有可能的质数（81 * 18 = 1458）。
我读了A和B，找出了可以通过将数字加起来生成的最大数字。如果B是2位数（最大数字是99，则为18）。
对于介于1和1之间的每个质数。我应用了整数分区算法。
对于每个可能的分区，我检查它们的数字平方和是否形成质数。如果是这样，则生成该分区的可能排列，并且如果它们处于范围内，则它们是幸运数字。
这是实现：
#include<stdio.h> #include<malloc.h> #include<math.h> #include <stdlib.h> #include<string.h> long long luckynumbers; int primelist[1500]; int checklucky(long long possible,long long a,long long b){ int prime =0; while(possible>0){ prime+=pow((possible%10),(float)2); possible/=10; } if(primelist[prime]) return 1; else return 0; } long long getmax(int numdigits){ if(numdigits == 0) return 1; long long maxnum =10; while(numdigits>1){ maxnum = maxnum *10; numdigits-=1; } return maxnum; } void permuteandcheck(char *topermute,int d,long long a,long long b,int digits){ if(d == strlen(topermute)){ long long possible=atoll(topermute); if(possible >= getmax(strlen(topermute)-1)){ // to skip the case of getting already read numbers like 21 and 021(permuted-210 if(possible >= a && possible <= b){ luckynumbers++; } } } else{ char lastswap ='\0'; int i; char temp; for(i=d;i<strlen(topermute);i++){ if(lastswap == topermute[i]) continue; else lastswap = topermute[i]; temp = topermute[d]; topermute[d] = topermute[i]; topermute[i] = temp; permuteandcheck(topermute,d+1,a,b,digits); temp = topermute[d]; topermute[d] = topermute[i]; topermute[i] = temp; } } } void findlucky(long long possible,long long a,long long b,int digits){ int i =0; if(checklucky(possible,a,b)){ char topermute[18]; sprintf(topermute,"%lld",possible); permuteandcheck(topermute,0,a,b,digits); } } void partitiongenerator(int k,int n,int numdigits,long long possible,long long a,long long b,int digits){ if(k > n || numdigits > digits-1 || k > 9) return; if(k == n){ possible+=(k*getmax(numdigits)); findlucky(possible,a,b,digits); return; } partitiongenerator(k,n-k,numdigits+1,(possible + k*getmax(numdigits)),a,b,digits); partitiongenerator(k+1,n,numdigits,possible,a,b,digits); } void calcluckynumbers(long long a,long long b){ int i; int numdigits = 0; long long temp = b; while(temp > 0){ numdigits++; temp/=10; } long long maxnum =getmax(numdigits)-1; int maxprime=0,minprime =0; temp = maxnum; while(temp>0){ maxprime+=(temp%10); temp/=10; } int start = 2; for(;start <= maxprime ;start++){ if(primelist[start]) { partitiongenerator(0,start,0,0,a,b,numdigits); } } } void generateprime(){ int i = 0; for(i=0;i<1500;i++) primelist[i] = 1; primelist[0] = 0; primelist[1] = 0; int candidate = 2; int topCandidate = 1499; int thisFactor = 2; while(thisFactor * thisFactor <= topCandidate){ int mark = thisFactor + thisFactor; while(mark <= topCandidate){ *(primelist + mark) = 0; mark += thisFactor; } thisFactor++; while(thisFactor <= topCandidate && *(primelist+thisFactor) == 0) thisFactor++; } } int main(){ char input[100]; int cases=0,casedone=0; long long a,b; generateprime(); fscanf(stdin,"%d",&cases); while(casedone < cases){ luckynumbers = 0; fscanf(stdin,"%lld %lld",&a,&b); int i =0; calcluckynumbers(a,b); casedone++; } }
该算法太慢。我认为答案可以根据数字的性质找到。请分享您的想法。谢谢。
出色的解决方案OleGG，但您的代码尚未优化。我对您的代码进行了以下更改，
它不需要在count_lucky函数中对k进行9 * 9 * i的处理，因为对于10000种情况，它将运行多次，相反，我通过开始和结束来减小了该值。
我已经使用ANS数组来存储中间结果。它看起来可能不多，但在10000多个案例中，这是减少时间的主要因素。
我已经测试了此代码，并通过了所有测试用例。这是修改后的代码：
#include <stdio.h> const int MAX_LENGTH = 18; const int MAX_SUM = 162; const int MAX_SQUARE_SUM = 1458; int primes[1460]; unsigned long long dyn_table[20][164][1460]; //changed here.......1 unsigned long long ans[19][10][164][1460]; //about 45 MB int start[19][163]; int end[19][163]; //upto here.........1 void gen_primes() { for (int i = 0; i <= MAX_SQUARE_SUM; ++i) { primes[i] = 1; } primes[0] = primes[1] = 0; for (int i = 2; i * i <= MAX_SQUARE_SUM; ++i) { if (!primes[i]) { continue; } for (int j = 2; i * j <= MAX_SQUARE_SUM; ++j) { primes[i*j] = 0; } } } void gen_table() { for (int i = 0; i <= MAX_LENGTH; ++i) { for (int j = 0; j <= MAX_SUM; ++j) { for (int k = 0; k <= MAX_SQUARE_SUM; ++k) { dyn_table[i][j][k] = 0; } } } dyn_table[0][0][0] = 1; for (int i = 0; i < MAX_LENGTH; ++i) { for (int j = 0; j <= 9 * i; ++j) { for (int k = 0; k <= 9 * 9 * i; ++k) { for (int l = 0; l < 10; ++l) { dyn_table[i + 1][j + l][k + l*l] += dyn_table[i][j][k]; } } } } } unsigned long long count_lucky (unsigned long long maxp) { unsigned long long result = 0; int len = 0; int split_max[MAX_LENGTH]; while (maxp) { split_max[len] = maxp % 10; maxp /= 10; ++len; } int sum = 0; int sq_sum = 0; unsigned long long step_result; unsigned long long step_; for (int i = len-1; i >= 0; --i) { step_result = 0; int x1 = 9*i; for (int l = 0; l < split_max[i]; ++l) { //changed here........2 step_ = 0; if(ans[i][l][sum][sq_sum]!=0) { step_result +=ans[i][l][sum][sq_sum]; continue; } int y = l + sum; int x = l*l + sq_sum; for (int j = 0; j <= x1; ++j) { if(primes[j + y]) for (int k=start[i][j]; k<=end[i][j]; ++k) { if (primes[k + x]) { step_result += dyn_table[i][j][k]; step_+=dyn_table[i][j][k]; } } } ans[i][l][sum][sq_sum] = step_; //upto here...............2 } result += step_result; sum += split_max[i]; sq_sum += split_max[i] * split_max[i]; } if (primes[sum] && primes[sq_sum]) { ++result; } return result; } int main(int argc, char** argv) { gen_primes(); gen_table(); //changed here..........3 for(int i=0;i<=18;i++) for(int j=0;j<=163;j++) { for(int k=0;k<=1458;k++) if(dyn_table[i][j][k]!=0ll) { start[i][j] = k; break; } for(int k=1460;k>=0;k--) if(dyn_table[i][j][k]!=0ll) { end[i][j]=k; break; } } //upto here..........3 int cases = 0; scanf("%d",&cases); for (int i = 0; i < cases; ++i) { unsigned long long a, b; scanf("%lld %lld", &a, &b); //changed here......4 if(b == 1000000000000000000ll) b--; //upto here.........4 printf("%lld\n", count_lucky(b) - count_lucky(a-1)); } return 0; }
说明：
gen_primes（）和gen_table（）几乎可以自我解释。
count_lucky（）的工作方式如下：
在split_max []中分割数字，只存储一位，几十个，几百个等位置的单位数字。这个想法是：假设split_map [2] = 7，所以我们需要计算结果
1在数百个位置中，所有00至99。
2在数百个位置上，所有00到99。
。。
在数百个位置中为7，所有00至99。
实际上，这是按照预先计算的位数和位数的平方和（在l循环中）完成的。对于此示例：和将在0到9 * i之间变化，平方和在0到9 * 9 * i之间变化…这是在j和k循环中完成的。在i循环中重复所有长度的操作
这就是OleGG的想法。
为了优化，考虑以下内容：
对于从0到9 * 9 * i的平方和而言，它是无用的，因为对于特定的数字和，它不会达到整个范围。就像如果i = 3并且总和等于5，那么平方和就不会在0到9 * 9 * 3之间变化。这部分使用预先计算的值存储在start []和end []数组中。
存储特定数字位数和特定数字在最高有效位的数值，并存储到特定的总和和平方的特定总和以进行存储。它太长，但仍约为45 MB。我相信这可以进一步优化。
