[UVa] 11099 - Next Same-Factored

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 11099 - Next Same-Factored
Source            : UVA Online Judge
Category          : Number Theory, Prime Factorization
Algorithm         : Number Theory
Verdict           : Accepted

#include"bits/stdc++.h"  
  
using namespace std;  
  
#define ll            long long int  
  
static const int maxn = 1e6 + 6;  
  
bool isPrime[maxn];  
vector <int> prime;  
  
inline void seive()  
{  
      fill(begin(isPrime), end(isPrime), true);  
      isPrime[0] = isPrime[1] = false;  
      for (int i = 4; i < maxn; i += 2) isPrime[i] = false;  
      for (int i = 3; i*i <= maxn; i += 2)  
      {  
            if (isPrime[i])  
            {  
                  for (int j = i*i; j < maxn; j += i+i) isPrime[j] = false;  
            }  
      }  
      prime.emplace_back(2);  
      for (int i = 3; i < maxn; i += 2)  
      {  
            if (isPrime[i]) prime.emplace_back(i);  
      }  
}  
  
vector <int> factor;  
  
inline void primeFactorization(ll n)  
{  
      for (int p : prime)  
      {  
            if (p*p > n) break;  
            if (n % p) continue;  
            factor.emplace_back(p);  
            while (n % p == 0) n /= p;  
      }  
      if (n > 1) factor.emplace_back(n);  
}  
  
ll n, next_n, len;  
bool found;  
  
inline void solve(int pos, ll num)  
{  
      if (num > n && num < next_n)  
      {  
            found = true;  
            next_n = num;  
            return;  
      }  
      if (pos >= len || num > 2000000 || num > next_n) return;  
      solve(pos, num * factor[pos]);  
      solve(pos+1, num * factor[pos]);  
      solve(pos+1, num);  
}  
  
int main()  
{  
      seive();  
      while (cin >> n)  
      {  
            if (n == 1)  
            {  
                  cout << "Not Exist!" << endl;  
                  continue;  
            }  
            factor.clear();  
            primeFactorization(n);  
            ll num = 1;  
            for (int p : factor) num *= p;  
            next_n = 2000000 - 1;  
            found = false;  
            len = factor.size();  
            solve(0, num);  
            if (found) cout << next_n << endl;  
            else cout << "Not Exist!" << endl;  
      }  
}