Menu
Problem A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky?
Input: The first line contains the number of test cases T. Each of the next T lines contains two integers, A and B.
Output: Output T lines, one for each case containing the required answer for the corresponding case.
Constraints:
1 <= T <= 10000
1 <= A <= B <= 10^18Sample Input:
2
1 20
120 130
Sample Output:
4
1
Explanation: For the first case, the lucky numbers are 11, 12, 14, 16. For the second case, the only lucky number is 120.
The problem is quite simple if we use brute force, however the running time is so critical that my program failed most test cases. My current idea is to use dynamic programming by storing the previous sum in a temporary array, so for example:sum_digits(10) = 1 -> sum_digits(11) = sum_digits(10) + 1
The same idea is applied for sum square but with counter equals to odd numbers. Unfortunately, it still failed 9 of 10 test cases which makes me think there must be a better way to solve it. Any idea would be greatly appreciated.
#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;
}
980
Seeing as A-B may be a range of 10^18 values, there's no way you can loop from A to B in time, no matter how optimized it gets. Let's try to figure out a way to do it that doesn't involve specifically considering all of those numbers...
First, let's reduce the problem to finding the lucky numbers between 1 and E, and call this lucky(E). The answer to the overall problem is simply lucky(B)-lucky(A-1).
Now let's construct such a lucky number digit by digit. Suppose we have already placed a few digits on this number and need to continue. Does it matter which digits we have already placed? No! We only need to know the following:
This will be what is called in dynamic programming as our state.
Let's disregard 10^18, as it's the only number in the input with 19 digits and it's not lucky. Note that E may have up to 18 digits, so we have 19 possibilities for n (from 0 to 18), 162 (18 * 9 + 1) possibilities for s, and 1459 (18 * 81 + 1) possibilities for sq. This leaves us with a search space of at most 5 million, which is incredibly smaller than searching 10^18 numbers for matches.
So let's define F(n, s, sq) as "in how many ways we can add digits to a number that has such properties to get a lucky number" (thanks to kilotaras for the rewording). The base case is when n equals the number of digits in E: F(N, s, s_sq) is 1 if s and sq are prime, 0 otherwise. For the other possibilities, do the possible transitions and call F recursively, taking care not to let the number you're constructing go over E.
In this manner, we can define lucky(E) as F(0, 0, 0).
When you're done, remember to memoize the function for the already calculated inputs/outputs.
Edit: This is a bit old, but here is a sample implementation of the lucky function, which I believe is correct. Note that n goes down in the code as opposed to the explanation above, as it's a lot easier to code it this way.
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);
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
