c++ - 動的計画法を最適化するには?

Question

問題数字の合計と数字の 2 乗の合計が素数である場合、数字はラッキーと呼ばれます。AとBの間でラッキーな数字は何個?

入力: 最初の行には、テスト ケースの数 T が含まれます。次の T 行にはそれぞれ、2 つの整数 A と B が含まれます。

出力: T 行を出力します。対応するケースに必要な回答を含むケースごとに 1 行です。

制約:
1 <= T <= 10000
1 <= A <= B <= 10^18

サンプル入力:

2

1 20

120 130

サンプル出力:

4

1

説明: 最初のケースでは、ラッキー ナンバーは 11、12、14、16 です。2 番目のケースでは、ラッキー ナンバーは 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までのラッキーナンバーを見つけることに減らし、これをラッキー（E）と呼びましょう。全体的な問題に対する答えは、単にラッキー（B）-ラッキー（A-1）です。

それでは、このようなラッキーナンバーを1桁ずつ作成してみましょう。この番号にすでに数桁の数字を入れて、続行する必要があるとします。すでに配置した数字は重要ですか？いいえ！次のことだけを知っておく必要があります。

• 何桁配置されたか（n）
• 現在の桁数の合計
• 現在の桁の二乗和（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）を「ラッキーナンバーを取得するためにそのようなプロパティを持つ数字に数字を追加できる方法はいくつあるか」と定義しましょう（言い換えてくれたキロタラに感謝します）。基本的なケースは、nがEの桁数に等しい場合です。F（N、s、s_sq）は、sとsqが素数の場合は1、それ以外の場合は0です。他の可能性については、可能な遷移を実行し、作成している番号がEを超えないように注意しながら、Fを再帰的に呼び出します。

このようにして、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を使用する必要があると思いますが、ハードコーディングするのではなく、プログラムの開始時に計算した方がよいでしょう。エラーが発生する可能性は低くなります。

作成できるキャッシュは他にもあります。すべての桁を調べて、それらとその平方を合計する必要があります。しかし、数字を1つずつ確認する必要があるとは誰も言いませんでした。一度に5桁を超えることができます。必要なのは、1000000セルの2つの配列で、1つは桁の合計を含み、もう1つは平方の合計を含みます。

つまり、素数の配列、すべての6桁の数値の桁の合計の配列、およびすべての6桁の数値の桁の2乗の合計の配列があります。18桁の数値の解を得るのは非常に簡単です。つまり、2つのモジュラス演算、2つの除算、4つの加算、および7つのルックアップがあります。これよりもはるかに速くなることはできません。

注：1000000の数字で遊んでください。L1キャッシュが小さい場合は、100000の方が速いかもしれませんが、1000000でも問題ないと思います。アクセスし続けるデータは、約2MBで、L1キャッシュ内にぴったり収まるはずです。