寻找幸运数字的算法

Question

寻找幸运数字的算法

我遇到了这个问题.如果数字的总和,以及其数字的平方和是素数,则称为幸运数字.A和B之间的幸运数字是多少？1 <= A <= B <= 10 ¹⁸.我试过这个.

首先,我生成了1之间所有可能的素数和可以通过求和平方得到的数字(81*18 = 1458).
我在A和B中读到了通过对数字求和可以产生的最大数量.如果B是2位数字(最大数字是由99生成的18).
对于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++;
        }

}

Run Code Online (Sandbox Code Playgroud)

算法太慢了.我认为可以根据数字的属性找到答案.请分享您的想法.谢谢.

Answer 1

pir*_*ate 15

优秀的解决方案OleGG,但您的代码未经过优化.我对您的代码进行了以下更改,

在count_lucky函数中,它不需要通过9*9*i来获取k,因为对于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;

}

Run Code Online (Sandbox Code Playgroud)

说明:

gen_primes()和gen_table()几乎是自我解释的.

count_lucky()的工作原理如下:

拆分split_max []中的数字,只存储1,数十,数百等位置的单个数字.这个想法是:假设split_map [2] = 7,所以我们需要计算结果

数百个位置,全部为00到99.

2位数百位,全部位于00至99位.

..

7在数百个位置,所有00到99.

这实际上是根据数字之和和已经预先处理的数字平方和来完成的(在l循环中).对于这个例子:sum将在0到9之间变化*i和square的总和将在0到9*9*i之间变化...这是在j和k循环中完成的.对于i循环中的所有长度重复此操作

这是OleGG的想法.

对于优化,考虑以下内容:

无用地运行从0到9*9*i的平方和,对于特定的数字总和,它不会达到整个范围.就像i = 3且sum等于5一样,则平方和不会从0变化到9*9*3.这部分使用预先计算的值存储在start []和end []数组中.
特定数字位数和特定数字的值在数字的最重要位置和特定总和以及特定的平方和存储用于记忆.它太长了但仍然大约45 MB.我相信这可以进一步优化.

Answer 2

Ole*_*eGG 14

您应该使用DP执行此任务.这是我的解决方案:

#include <stdio.h>

const int MAX_LENGTH = 18;
const int MAX_SUM = 162;
const int MAX_SQUARE_SUM = 1458;
int primes[1459];
long long dyn_table[19][163][1459];

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];
                }
            }
        }
    }
}

long long count_lucky (long long max) {
            long long result = 0;
    int len = 0;
    int split_max[MAX_LENGTH];
    while (max) {
        split_max[len] = max % 10;
        max /= 10;
        ++len;
    }
    int sum = 0;
    int sq_sum = 0;
    for (int i = len-1; i >= 0; --i) {
        long long step_result = 0;
        for (int l = 0; l < split_max[i]; ++l) {
            for (int j = 0; j <= 9 * i; ++j) {
                for (int k = 0; k <= 9 * 9 * i; ++k) {
                    if (primes[j + l + sum] && primes[k + l*l + sq_sum]) {
                        step_result += dyn_table[i][j][k];
                    }
                }
            }
        }
        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();

    int cases = 0;
    scanf("%d", &cases);
    for (int i = 0; i < cases; ++i) {
        long long a, b;
        scanf("%lld %lld", &a, &b);
        printf("%lld\n", count_lucky(b) - count_lucky(a-1));
    }
    return 0;
}

Run Code Online (Sandbox Code Playgroud)

简要说明:

我正在使用Eratosthenes方法计算所有素数达到9*9*MAX_LENGTH;
后来,使用DP,我建表dyn_table其中值X在dyn_table [i] [j] [k]的意思是,我们恰好有X号的长度我用的数字等于总和Ĵ它的平方等于和总和ķ
然后我们可以轻松地计算从1到999..999(len次数为9)的幸运数量.为此我们只总结了所有dyn_table [len] [j] [k],其中j和k都是素数.
为了计算从1到随机X的幸运数量,我们将间隔从1到X分成长度等于10 ^ K的间隔(参见*count_lucky*函数).
我们的最后一步是从count_lucky(b)中减去count_lucky(a-1)(因为我们在我们的间隔中包括一个).

就这样.对于O(log(MAX_NUMBER)^ 3)的预计算工作,每一步都具有这种复杂性.

我已经针对线性直接测试我的解决方案,结果是相同的

归档时间：	13 年，7 月前
查看次数：	15685 次
最近记录：	7 年，8 月前