I would have understood if it would’ve got TLE but the problem keeps giving wrong answer on submission…_
Here’s the code
#include <bits/stdc++.h>
#define int long long
using namespace std;
unordered_map<int, bool> primes;
int dp[20][2];
int gcd(int a, int b){
return (!b) ? a : gcd(b, a % b);
}
bool check(string s){
int number = stoll(s + string());
bool result = true;
for(int i = 0;i<s.length() - 1;i++){
if(gcd(stoll(s[i] + string()), stoll(s[i + 1] + string())) == 1){
result = false;
break;
}
}
if(result){
for(char c : s){
if(primes[stoll(c + string())] == true && number % stoll(c + string()) != 0){
return false;
}
}
}
return result;
}
int go(string s, int pos = 0, int tight = 1, string x = ""){
if(pos == s.length()){
if(check(x)){
return 1;
}
else{
return 0;
}
}
if(dp[pos][tight] != -1) return dp[pos][tight];
if(tight == 1){
int res = 0;
for(int i = 0;i<=s[pos] - '0';i++){
if(i == s[pos] - '0'){
res += go(s, pos + 1, 1, x + to_string(i));
}
else{
res += go(s, pos + 1, 0, x + to_string(i));
}
}
return dp[pos][tight] = res;
}
else{
int res = 0;
for(int i = 0;i<=9;i++){
res += go(s, pos + 1, 0, x + to_string(i));
}
return dp[pos][tight] = res;
}
}
void solve(int a, int b){
memset(dp, -1, sizeof(dp));
int lo = go(to_string(a - 1));
memset(dp, -1, sizeof(dp));
int hi = go(to_string(b));
cout <<hi - lo<<'\n';
}
int32_t main(){
primes[2] = true;
primes[3] = true;
primes[5] = true;
primes[7] = true;
int t;
cin >>t;
while(t--){
int a, b;
cin >>a>>b;
solve(a, b);
}
return 0;
}