Блог пользователя prathams

Автор prathams, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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