How to solve it

Revision en2, by prathams, 2015-07-18 10:13:07

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×109.

Output modulo 101.

I got this problem on link

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;               
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English prathams 2015-07-18 10:13:07 888 Tiny change: 'w code :\n\n~~~~~~\n\n#include' -
en1 English prathams 2015-07-17 20:38:08 394 Initial revision (published)