We call a natural number supernatural if it does not contain any ones in its decimal representation and the product of its digits is equal to n. For given n, find how many supernatural numbers exist.↵
↵
**Constraint** : The input contains a single integer n not exceeding $\ 2×10^9 $.↵
↵
Output modulo 101.↵
↵
I got this problem on [link](http://www.e-olymp.com/en/problems/6082)↵
↵
**UPD** : I solved this problem but only 80% test cases are passing, rest giving TLE, can anyone please suggest how can i improve the below code using some trick or memoization:↵
↵
~~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define MOD 101↵
#define LL long long↵
#define out(x) cout << #x << " : " << x << "\n";↵
↵
bool isPrime(LL n) {↵
for(LL i = 2;i * i <= n; i++) {↵
if(n % i == 0) return false;↵
}↵
return true;↵
}↵
↵
LL ans = 0;↵
↵
void solve(LL n) {↵
if(n <= 1) return;↵
if(isPrime(n)) {↵
if(n < 10) ans = (ans + 1) % MOD;↵
return;↵
}↵
if(n < 10) ans = (ans + 1) % MOD;↵
for(int i = 2;i < 10;i++) {↵
if(n % i == 0)↵
solve(n / i);↵
} ↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
LL n; cin >> n;↵
solve(n);↵
cout << ans << endl;↵
return 0; ↵
}↵
↵
~~~~~~
↵
**Constraint** : The input contains a single integer n not exceeding $\ 2×10^9 $.↵
↵
Output modulo 101.↵
↵
I got this problem on [link](http://www.e-olymp.com/en/problems/6082)↵
↵
**UPD** : I solved this problem but only 80% test cases are passing, rest giving TLE, can anyone please suggest how can i improve the below code using some trick or memoization:↵
↵
~~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define MOD 101↵
#define LL long long↵
#define out(x) cout << #x << " : " << x << "\n";↵
↵
bool isPrime(LL n) {↵
for(LL i = 2;i * i <= n; i++) {↵
if(n % i == 0) return false;↵
}↵
return true;↵
}↵
↵
LL ans = 0;↵
↵
void solve(LL n) {↵
if(n <= 1) return;↵
if(isPrime(n)) {↵
if(n < 10) ans = (ans + 1) % MOD;↵
return;↵
}↵
if(n < 10) ans = (ans + 1) % MOD;↵
for(int i = 2;i < 10;i++) {↵
if(n % i == 0)↵
solve(n / i);↵
} ↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false); cin.tie(NULL);↵
LL n; cin >> n;↵
solve(n);↵
cout << ans << endl;↵
return 0; ↵
}↵
↵
~~~~~~
