prathams's blog

By prathams, history, 4 years ago, In English,

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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

That number must have only 2,3,5 or 7 as prime divisors. Make 4 dimensional state (num2, num3, num5, num7) and solve it with dinamic programming.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Try working with factoring. Maybe getting the factors of N would lead you to the right idea.

EX: 8 = 2 * 2 * 2. And the numbers are 42, 24, 222, 8

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by prathams (previous revision, new revision, compare).

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry for writing here after 4 years, but probably this will help someone who decided to google this problem.

The main idea is, as noticed by TMandzu, that n which have prime divisors bigger than 7 will have 0 supernatural numbers. But we need to check this before solving anything, because factoring number in solve function, as prathams did, is very slow. We can do this with trial division in sqrt(N) (actually, a lot faster because we can break when we reach n%7 != 0 and n != 1). After this we need to write solve function almost like TC did, but we can use unordered_map to do memorization.

ll solve(ll n) {
   ll ans = 0;
   if(n == 1 || n == 2 || n == 3 || n == 5 || n == 7)
      return 1;
   if(memo.count(n) != 0)
      return memo[n];
   for(int i = 2; i <= 9; ++i) {
      if(n%i == 0)
         ans = (ans%101 + solve(n/i)%101)%101;
   }
   return memo[n] = ans;
}

Hope someone will find this helpful.