如何优化动态规划？

Question

问题：如果一个数字的各位数字之和和各位数字的平方和都是质数，则称该数字为幸运数字。在A和B之间有多少个幸运数字？

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

输出：对于每个测试用例，输出一行包含所需答案的结果。

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

思路：使用暴力法可以解决问题，但运行时间关键，程序无法通过大多数测试用例。使用动态规划将前一次的求和存储在临时数组中，例如: 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;
}

- roxrook

---

嗯...你能用递归的方式解决这个问题吗（无论是暴力还是其他方法）？我不是说强制使用递归--我的意思是，你是否能自然地看到如何通过子问题递归地解决它？ - user541686

由于这个问题被归类为“动态规划”，我从未考虑过递归方法。在我的解决方案中，递归公式实际上涉及到了先前的和/平方和。不幸的是，它仍然不够好。我甚至不得不使用素数表，而不是编写检查素数的函数。 - roxrook

我自己还没有做过这个，但从问题的外观来看，它似乎只是 让我们将递归斐波那契算法从指数级改进为多项式级 问题的伪装。我认为一个质数表可能就可以了——目标只是防止您进行指数级递归（或等效迭代）。 - user541686

我昨天尝试了Rabin Miller算法，但是失败了。此外，质数范围仅从1->18 * 81 + 1变化，这就是为什么我决定使用质数表的原因。 - roxrook

是的，这确实有帮助。感谢分享你的想法。改变问题的想法似乎非常有趣。 - roxrook

Answer 1

考虑到A-B的范围可能达到10^18，无论如何进行优化，都不能在时间上循环从A到B。我们来想办法解决这个问题，而不是专门考虑所有这些数字……

首先，让我们把问题简化为找出1到E之间的幸运数字，并称其为lucky(E)。整体问题的答案就是lucky(B)-lucky(A-1)。

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

已放置的数字数量（n）

当前数字之和（s）

当前数字平方和（sq）

这将成为动态规划中所谓的“状态”。

让我们忽略10^18，因为它是输入中唯一具有19个数字且不幸运的数字。请注意，E可能具有高达18个数字，因此n有19种可能性（从0到18），s有162种可能性（18 * 9 + 1），sq有1459种可能性（18 * 81 + 1）。这使我们的搜索空间最多不超过500万，比搜索10^18个匹配数字要小得多。

因此，让我们将F(n, s, sq)定义为“我们可以添加数字以获得幸运数字的方式的数量”，（感谢kilotaras重新措辞）。基本情况是当n等于E的位数时：如果s和sq是质数，则F(N, s, s_sq)为1，否则为0。对于其他可能性，执行可能的转换并递归调用F，注意不要让您正在构建的数字超过E。

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

完成后，请记得为已计算的输入/输出备忘录函数。

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

- ffao

---

我们可以将lucky(E)定义为F(0, 0, 0)。F(N, s, s_sq)如果s和s_sq是质数，则为1。你如何考虑所有可能的求和变化？例如：23与32？DP思想很完美，但以目前的形式不起作用... - Karoly Horvath

F(N, s, sq)的意思是“我们可以以多少种方式添加数字到一个具有这样属性的数字上，以获得幸运数字”。我们只能添加零个数字（这是一种方式）。 - kilotaras

这是一个旧的线程，但我很好奇你如何“注意不要让你构造的数字超过E”。 - danqing

尽管我理解这个想法，但我无法找到解决这个问题的方法。在过去的几个月里，我一直在练习 DP 算法。我意识到这种类型的问题非常普遍，但我还没有找到一个全面解释它的完整解决方案。因此，我想问一下能否提供一个可行的解决方案？我只是想看看正确的做法。 - roxrook

通过给一个数字添加数字，我无法看出在这种情况下它所暗示的数字是什么，例如如果我从123开始，应该从哪个数字开始？我尝试反过来考虑所有的和都是质数并将其分解为数字，但我无法想出一个可行的递归。您能否添加更多细节？谢谢。 - roxrook

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缓存中。

- zmbq

---

缓存质数判断是正确的。但是如果每次都循环检查每个数字，即使可以使用查找进行求和，也不会有任何进展。 - nhahtdh