PROBLEM LINK:
Author: Naman Singh
Tester: Adwita Arora
Editorialist: Madhavi Dixit
DIFFICULTY:
EASY
PREREQUISITES:
XOR logical operator, Sieve algorithm
PROBLEM:
To find number of prime numbers in the given range such that the xor of their digits is a prime too.
QUICK EXPLANATION:
In this problem, l and r being two integer values, such that the prime numbers lying within the range [l,r] must satisfy the condition such that the logical XOR operation of all the digits is also a prime number. We need to find the sum of these numbers in the given range.
EXPLANATION:
The problem relies on the use of pre-computation. We will define an array called csum[] which at each index stores the sum of those primes satisfying the brief upto its corresponding whole number. The 0th element contains 0 since 0 is not prime.
As it is evident from the source code (given below), in the user defined function sieve_generate, every integer value (within the defined range) is checked whether it is prime or not, if the number is prime; true value is returned otherwise we get a false value.
Next, we run a loop for all whole numbers starting from 1 upto the maximum limit. Within the loop, the current index of csum stores in itself the preceding value of the array.
Next we determine whether the current whole number being considered satisfies the brief - being prime itself and having the XOR of its digits as prime. If true, then this number gets added to the current value of the csum array.
In this way each element of csum stores the sum of all eligible primes upto that index. The example below will further illustrate the problem:
Here we have taken a basic example where l=1 and r=10. The boxes represent the csum[] array with each element written below its corresponding natural number. The numbers which are prime are written in green. Since they all have single digits they satisfy both prerequisites.
Figure
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define MAX 1'00'005
bool is_prime[MAX];
void sieve_generate(){
for(int i=0; i<MAX; ++i){
is_prime[i] = (i&1);
}
is_prime[0] = is_prime[1] = false;
is_prime[2] = true;
for(int i=3; i*i<MAX; i+=2){
if(is_prime[i]){
for(int j=i*i; j<MAX; j+=2*i){
is_prime[j] = false;
}
}
}
}
int digits_xor(int num){
int ans = 0;
while(num){
ans ^= (num%10);
num /= 10;
}
return ans;
}
long long csum[MAX];
void init(){
sieve_generate();
csum[0] = 0;
for(int i=1; i<MAX; ++i){
csum[i] = csum[i-1];
// cout << i << " " << (is_prime[i] && is_prime[digits_xor(i)]) << endl;
if(is_prime[i] && is_prime[digits_xor(i)]){
csum[i] += i;
}
}
}
int main(){
init();
int t;
cin >> t;
while(t--){
int l, r;
cin >> l >> r;
cout << csum[r] - csum[l-1] << endl;
}
return 0; }