我发现了这个问题。一个数字被称为“幸运数”，当它的各位数字之和以及各位数字的平方之和都是质数时。在A和B之间有多少个幸运数？1 <= A <= B <= 10^18。我尝试了以下步骤。
- 首先我生成了在1到可以通过求平方和得到的数字之间的所有可能的质数（81 * 18 = 1458）。
- 我读入A和B，找出可以通过加总各位数字得出的最大数字。如果B是两位数，则最大数字为18（由99生成）。
- 对于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++;
}
}
算法速度太慢了。我认为可以根据数字的属性找到答案。请分享你的想法。谢谢。
primelist的维度为1400，但您将其视为具有1500个维度。 - Paul R