c++ - 如何优化动态规划？

Question

问题如果一个数字的数字之和以及其数字的平方和是质数，则该数字称为幸运数字。A和B之间有多少个数字是幸运的？

输入： 第一行包含测试用例 T 的数量。接下来的 T 行中的每一行包含两个整数，A 和 B。

输出： 输出 T 行，每个案例一个包含相应案例所需的答案。

约束：
1 <= T <= 10000
1 <= A <= B <= 10^18

样本输入：

2

1 20

120 130

样本输出：

4

1

解释： 第一种情况，幸运数字是11、12、14、16。第二种情况，唯一的幸运数字是120。

如果我们使用蛮力，问题就很简单，但是运行时间非常关键，以至于我的程序在大多数测试用例中都失败了。我目前的想法是通过将先前的总和存储在一个临时数组中来使用动态编程，例如：
sum_digits(10) = 1 -> sum_digits(11) = sum_digits(10) + 1
同样的想法适用于平方和，但计数器等于奇数。不幸的是，它仍然失败了 10 个测试用例中的 9 个，这让我认为必须有更好的方法来解决它。任何想法将不胜感激。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <cassert>
#include <bitset>

using namespace std;

bool prime_table[1540] = {
    0, 0, 1, 1, 0, 1, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 
    1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 
    0 
};

unsigned num_digits(long long i) {
    return i > 0 ? (long) log10 ((double) i) + 1 : 1;
}

void get_sum_and_sum_square_digits(long long n, int& sum, int& sum_square) {
    sum = 0;
    sum_square = 0;
    int digit;
    while (n) {
        digit = n % 10;
        sum += digit;
        sum_square += digit * digit;
        n /= 10;
    }
}

void init_digits(long long n, long long previous_sum[], const int size = 18) {
    int current_no_digits = num_digits(n);
    int digit;
    for (int i = 0; i < current_no_digits; ++i) {
        digit = n % 10;
        previous_sum[i] = digit;
        n /= 10;
    }   

    for (int i = current_no_digits; i <= size; ++i) {
        previous_sum[i] = 0;
    }   
}

void display_previous(long long previous[]) {
    for (int i = 0; i < 18; ++i) {
        cout << previous[i] << ",";
    }
}

int count_lucky_number(long long A, long long B) {
    long long n = A;
    long long end = B;
    int sum = 0;
    int sum_square = 0;
    int lucky_counter = 0;

    get_sum_and_sum_square_digits(n, sum, sum_square);

    long long sum_counter = sum;
    long long sum_square_counter = sum_square;

    if (prime_table[sum_counter] && prime_table[sum_square_counter]) {
        lucky_counter++;
    }

    long long previous_sum[19] = {1};

    init_digits(n, previous_sum);

    while (n < end) {
        n++;
        if (n % 100000000000000000 == 0) {
            previous_sum[17]++;
            sum_counter = previous_sum[17] + previous_sum[18];
            sum_square_counter = previous_sum[17] * previous_sum[17] + previous_sum[18] * previous_sum[18];

            previous_sum[16] = 0;
            previous_sum[15] = 0;
            previous_sum[14] = 0;
            previous_sum[13] = 0;
            previous_sum[12] = 0;
            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10000000000000000 == 0) {
            previous_sum[16]++;
            sum_counter = previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[15] = 0;
            previous_sum[14] = 0;
            previous_sum[13] = 0;
            previous_sum[12] = 0;
            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 1000000000000000 == 0) {
            previous_sum[15]++;

            sum_counter = previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[14] = 0;
            previous_sum[13] = 0;
            previous_sum[12] = 0;
            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 100000000000000 == 0) {
            previous_sum[14]++;

            sum_counter = previous_sum[14] + previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[13] = 0;
            previous_sum[12] = 0;
            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10000000000000 == 0) {
            previous_sum[13]++;

            sum_counter = previous_sum[13] + previous_sum[14] + previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[12] = 0;
            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 1000000000000 == 0) {
            previous_sum[12]++;

            sum_counter = previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[11] = 0;
            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 100000000000 == 0) {
            previous_sum[11]++;

            sum_counter = 
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[10] = 0;
            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10000000000 == 0) {
            previous_sum[10]++;

            sum_counter = 
                previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[9] = 0;
            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 1000000000 == 0) {
            previous_sum[9]++;

            sum_counter = 
                previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];


            previous_sum[8] = 0;
            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 100000000 == 0) {
            previous_sum[8]++;

            sum_counter = 
                previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[7] = 0;
            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10000000 == 0) {
            previous_sum[7]++;

            sum_counter = 
                previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[6] = 0;
            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 1000000 == 0) {
            previous_sum[6]++;

            sum_counter = 
                previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[5] = 0;
            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 100000 == 0) {
            previous_sum[5]++;

            sum_counter = previous_sum[5] + previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] + previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] + previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[5] * previous_sum[5] +
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[4] = 0;
            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10000 == 0) {
            previous_sum[4]++;

            sum_counter = 
                previous_sum[4] + previous_sum[5] + 
                previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[4] * previous_sum[4] +
                previous_sum[5] * previous_sum[5] +
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[3] = 0;
            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 1000 == 0) {
            previous_sum[3]++;

            sum_counter = 
                previous_sum[3] + previous_sum[4] + previous_sum[5] + 
                previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[3] * previous_sum[3] +
                previous_sum[4] * previous_sum[4] +
                previous_sum[5] * previous_sum[5] +
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[2] = 0;
            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 100 == 0) {
            previous_sum[2]++;

            sum_counter = 
                previous_sum[2] + previous_sum[3] + previous_sum[4] + previous_sum[5] + 
                previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[2] * previous_sum[2] +
                previous_sum[3] * previous_sum[3] +
                previous_sum[4] * previous_sum[4] +
                previous_sum[5] * previous_sum[5] +
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[1] = 0;
            previous_sum[0] = 0;
        }
        else if (n % 10 == 0) {
            previous_sum[1]++;

            sum_counter = 
                previous_sum[1] + previous_sum[2] + previous_sum[3] + previous_sum[4] + previous_sum[5] + 
                previous_sum[6] + previous_sum[7] + previous_sum[8] + previous_sum[9] + previous_sum[10] +
                previous_sum[11] + previous_sum[12] + previous_sum[13] + previous_sum[14] + previous_sum[15] +
                previous_sum[16] + previous_sum[17] + previous_sum[18];

            sum_square_counter = 
                previous_sum[1] * previous_sum[1] + 
                previous_sum[2] * previous_sum[2] +
                previous_sum[3] * previous_sum[3] +
                previous_sum[4] * previous_sum[4] +
                previous_sum[5] * previous_sum[5] +
                previous_sum[6] * previous_sum[6] +
                previous_sum[7] * previous_sum[7] +
                previous_sum[8] * previous_sum[8] +
                previous_sum[9] * previous_sum[9] +
                previous_sum[10] * previous_sum[10] +
                previous_sum[11] * previous_sum[11] +
                previous_sum[12] * previous_sum[12] +
                previous_sum[13] * previous_sum[13] +
                previous_sum[14] * previous_sum[14] +
                previous_sum[15] * previous_sum[15] +
                previous_sum[16] * previous_sum[16] +
                previous_sum[17] * previous_sum[17] +
                previous_sum[18] * previous_sum[18];

            previous_sum[0] = 0;
        }
        else {
            sum_counter++;
            sum_square_counter += ((n - 1) % 10) * 2 + 1;
        }

        // get_sum_and_sum_square_digits(n, sum, sum_square);
        // assert(sum == sum_counter && sum_square == sum_square_counter);
        if (prime_table[sum_counter] && prime_table[sum_square_counter]) {
            lucky_counter++;
        }
    }

    return lucky_counter;
}


void inout_lucky_numbers() {
    int n;
    cin >> n;

    long long a;
    long long b;

    while (n--) {
        cin >> a >> b;
        cout << count_lucky_number(a, b) << endl;
    }
}

int main() {
    inout_lucky_numbers();

    return 0;
}

Answer 1

鉴于 AB 可能是 10^18 个值的范围，因此无论它得到多么优化，您都无法及时从 A 循环到 B。让我们尝试找出一种不涉及专门考虑所有这些数字的方法......

首先，让我们将问题简化为找到 1 和 E 之间的幸运数字，并将其称为lucky(E)。整个问题的答案很简单：lucky(B)-lucky(A-1)。

现在让我们逐位构造这样一个幸运数字。假设我们已经在这个数字上放置了几位数字，需要继续。我们已经放置了哪些数字有关系吗？不！我们只需要知道以下几点：

• 已放置多少位 (n)
• 当前数字总和 (s)
• 当前数字平方和 (sq)

这就是我们在动态规划中所说的状态。

让我们忽略 10^18，因为它是输入中唯一的 19 位数字，而且它并不幸运。请注意，E 最多可以有 18 位数字，所以我们有 19 种可能的 n（从 0 到 18）、162（18 * 9 + 1）种可能的 s 和 1459（18 * 81 + 1）种可能的 sq。这给我们留下最多 500 万的搜索空间，这比搜索 10^18 个数字来匹配要小得多。

因此，让我们将 F(n, s, sq) 定义为“我们可以通过多少种方式向具有此类属性的数字添加数字以获得幸运数字”（感谢 kitaras 的改写）。基本情况是当 n 等于 E 中的位数时：如果 s 和 sq 是素数，则 F(N, s, s_sq) 为 1，否则为 0。对于其他可能性，进行可能的转换并递归调用 F，注意不要让你正在构建的数字超过 E。

通过这种方式，我们可以将 lucky(E) 定义为 F(0, 0, 0)。

完成后，请记住记住已计算的输入/输出的函数。

编辑：这有点旧，但这是幸运函数的示例实现，我认为这是正确的。请注意，与上面的解释相反，代码中的 n 下降了，因为这样编码要容易得多。

long long dp[20][163][1460];
bool calc[20][163][1460];

int digits[20];
int digit_cnt;

// The last argument (eq) is used to avoid going over E
long long F(int n, int s, int sq, bool eq) {
    // Base cases
    if (!eq && calc[n][s][sq]) return dp[n][s][sq];
    if (n == 0) return (prime_table[s] && prime_table[sq]);

    long long resp = 0;

    // Test all possibilities for the next digit
    for (int d = 0; d < 10; d++) {
        if (!eq || digits[n-1] > d) {
            resp += F(n-1, s+d, sq + d*d, false);
        }

        // If the number formed so far is exactly equal to E
        // we will go over E if we pick a larger
        // digit than digits[n-1]. 
        // So we have to take care if eq == true
        else if (digits[n-1] == d) {
            resp += F(n-1, s+d, sq + d*d, true);
        }
        else break;
    }

    // Note that computations that have eq set to true
    // can't be used in other calculations of F(), as they depend on E.
    if (!eq) {
        calc[n][s][sq] = true;
        dp[n][s][sq] = resp;
    }

    return resp;
}

long long lucky(long long E) {
    long long tE = E;
    digit_cnt = 0;

    while (tE) {
        digits[digit_cnt++] = tE % 10;
        tE /= 10;
    }

    return F(digit_cnt, 0, 0, true);
}

Answer 2

检查一个数字是否是素数非常容易，您将遇到的最高数字是 1458（对于数字 999,999,999,999,999,999）。我想这就是你拥有 的原因prime_table，这很好。因此，查找特定数字是否为素数不能更快。我认为您绝对应该使用您拥有的 prime_table，尽管如果您在程序开始时计算它会更好，而不是对其进行硬编码 - 出错的机会更少。

您可以创建其他缓存。您需要遍历所有数字并将它们和它们的平方相加。但是没有人说你应该一个一个地检查数字。您一次可以超过 5 位数字 - 您只需要两个包含 1000000 个单元格的数组，一个包含数字总和，一个包含平方和。

所以，你有一个素数数组，一个所有 6 位数字的数字和的数组，以及一个所有 6 位数字的数字平方和的数组。获得任何 18 位数字的解决方案将非常容易 - 您有 2 个模运算、2 个除法、4 个加法和 7 个查找。你不能比这更快。

注意：玩 1000000 数字。如果您的 L1 缓存很小，100000 可能会更快，尽管我相信 1000000 您仍然可以 - 您有大约 2MB 的数据不断访问，这应该适合您的 L1 缓存。