Как оптимизировать динамическое программирование?

Question

Задача Число называется удачливым, если сумма его цифр, а также сумма квадратов его цифр - это простое число. Сколько номеров между A и B повезло?

Входной сигнал: Первая строка содержит количество тестовых примеров Т. Каждая из следующих T строк содержит два целых числа, А и В.

Выход: Т выходных линий, по одному для каждого случая, содержащего требуемый ответ для соответствующего случая.

Ограничения:
= Т < = 10000
= A < = B < = 10^18

Пример входных сигналов:

Образец Выход:

Пояснение: В первом случае, счастливые числа 11, 12, 14, 16. Для второй случай, единственное счастливое число - 120.

Проблема довольно просто, если мы используем грубую силу, однако время работы настолько критично, что моя программа провалила большинство тестовых случаев. Моя нынешняя идея - использовать динамическое программирование, сохраняя предыдущую сумму во временном массиве, например:
sum_digits(10) = 1 -> sum_digits(11) = sum_digits(10) + 1
Эта же идея применяется к сумме квадратов, но счетчик равен нечетным числам. К сожалению, все еще не удалось выполнить 9 из 10 тестовых случаев, из-за чего я думаю, что должен быть лучший способ его решить. Любая идея была бы весьма признательна.

#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

Видя, как A-B может быть диапазоном 10^18 значений, нет никакого способа, вы можете цикл от А до Б во время, независимо от того, насколько оптимизирован он получает. Давайте попробуем выяснить, как это сделать, что не связано конкретно с учетом всех этих чисел ...

Во-первых, давайте уменьшим проблему до нахождения счастливых чисел от 1 до E и позвоним этому повезло (E). Ответ на общую проблему - просто удача (B) -lucky (A-1).

Теперь давайте построим такую ​​счастливую цифру по цифре. Предположим, мы уже поместили несколько цифр на это число и должны продолжить. Имеет ли значение, какие цифры мы уже разместили? Нет!Нам нужно только знать следующее:

• Сколько цифр размещенными (п)
• Текущая сумма цифр (ы)
• Текущая сумма квадратов цифр (кв)

Это будет так называемое динамическое программирование как наше состояние.

Давайте проигнорируем 10^18, так как это единственное число на входе с 19 цифрами, и это не повезло. Заметим, что E может иметь до 18 цифр, поэтому у нас есть 19 возможностей для n (от 0 до 18), 162 (18 * 9 + 1) возможностей для s и 1459 (18 * 81 + 1) возможностей для sq. оставляет нас с поисковым пространством не более 5 миллионов, что невероятно меньше, чем поиск 10^18 номеров для матчей.

Итак, давайте определим F (n, s, sq) как «во сколько способов мы можем добавить цифры к числу, у которого есть такие свойства, чтобы получить счастливое число» (спасибо китарам для перезаписи). Основной случай - когда n равно числу цифр в E: F (N, s, s_sq) равно 1, если s и sq простые, 0 в противном случае. Для других возможностей сделайте возможные переходы и вызовите F рекурсивно, стараясь не допустить, чтобы число, которое вы строите, перешло E.

Таким образом, мы можем определить счастливый (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, что хорошо. Поэтому поиск, если конкретный номер является простым, не может быть быстрее. Я думаю, что вы обязательно должны использовать премьер-стол, который у вас есть, хотя было бы лучше, если бы вы рассчитали его в начале программы, вместо жесткого кодирования - меньше шансов на ошибку.

Есть и другие кеши, которые вы можете создать. Вам нужно пройти все цифры и суммировать их и их квадраты. Но никто не сказал, что вы должны перебирать цифры один за другим. Вы можете перейти на 5 цифр сразу - все, что вам нужно, это два массива со 1000000 ячейками, один из которых содержит сумму цифр и цифру, содержащую сумму квадратов.

Итак, у вас есть массив для простых чисел, массив для суммы цифр для всех чисел с 6 цифрами и массив для суммы квадратов цифр для всех чисел с 6 цифрами. Получение решения для любого 18-значного числа будет очень простым - у вас есть 2 modulu-операции, 2 подразделения, 4 дополнения и 7 поисковых запросов. Вы не можете получить гораздо быстрее, чем это.

Примечание: играйте с фигурой 1000000. 100000 может быть быстрее, если ваш кеш L1 невелик, хотя я считаю, что с 1000000 вы все еще в порядке - у вас есть около 2 МБ данных, которые вы продолжаете получать, что должно уместиться внутри вашего кеша L1.