[Spoj] PUCMMT02 - Square-Free Product (Hard)

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : PUCMMT02 - Square-Free Product (Hard)
Source            : Spoj 
Category          : Number Theory
Algorithm         : Pollard Rho Prime Factorization
Verdict           : Accepted

#include "bits/stdc++.h"  
   
using namespace std;  
   
namespace Rho  // Implementation: s_h_shahin, du
{  
      mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());  
   
      const int MAXP = 1000010;  
      const int BASE[] = {2, 450775, 1795265022, 9780504, 28178, 9375, 325};  
   
      long long seq[MAXP];  
      int primes[MAXP];  
      int spf[MAXP];  
   
      inline long long mod_add(long long x, long long y, long long m)  
      {  
            x += y;  
            if (x >= m) x -= m;  
            return x;  
      }  
      inline long long mod_mul(long long x, long long y, long long m)  
      {  
            long long res = x * y - (long long)((long double)x * y / m + 0.5) * m;  
            return res < 0 ? res + m : res;  
      }  
      inline long long mod_pow(long long x, long long p, long long m)  
      {  
            long long res = 1 % m;  
            for ( ; p; p >>= 1)  
            {  
                  if (p & 1) res = mod_mul(res, x, m);  
                  x = mod_mul(x, x, m);  
            }  
            return res;  
      }  
      // O(k * logn * logn * logn), k = number of rounds performed  
      inline bool miller_robin(long long n)  
      {  
            if (n <= 2 or (~n & 1)) return (n == 2);  
            if (n < MAXP) return spf[n] == n;  
            long long c;  
            long long d;  
            long long s = 0;  
            long long r = n - 1;  
            while (~r & 1)  
            {  
                  s++;  
                  r >>= 1;  
            }  
            // each iteration is a round  
            for (int i = 0; primes[i] < n and primes[i] < 32; i++)  
            {  
                  c = mod_pow(primes[i], r, n);  
                  for (int j = 0; j < s; j++)  
                  {  
                        d = mod_mul(c, c, n);  
                        if (d == 1 and c != 1 and c != (n - 1)) return false;  
                        c = d;  
                  }  
                  if (c != 1) return false;  
            }  
            return true;  
      }  
      inline void sieve()  
      {  
            int cnt = 0;  
            for (int i = 2; i < MAXP; i++)  
            {  
                  if (spf[i] == 0) primes[cnt++] = spf[i] = i;  
                  for (int j = 0; 1LL * i * primes[j] < MAXP; j++)  
                  {  
                        spf[i * primes[j]] = primes[j];  
                        if (spf[i] == spf[i * primes[j]]) break;  
                  }  
            }  
      }  
      // expected complexity O(n ^ 1/4)  
      long long pollard_rho(long long n)  
      {  
            while (true)  
            {  
                  long long x = rand() % n;  
                  long long y = x;  
                  long long c = rand() % n;  
                  long long u = 1;  
                  long long v;  
                  long long t = 0;  
                  long long *px = seq;  
                  long long *py = seq;  
                  while (true)  
                  {  
                        *py++ = y = mod_add(mod_mul(y, y, n), c, n);  
                        *py++ = y = mod_add(mod_mul(y, y, n), c, n);  
                        if ((x = *px++) == y) break;  
                        v = u;  
                        u = mod_mul(u, abs(y - x), n);  
                        if (u == 0) return __gcd(v, n);  
                        if (++t == 32)  
                        {  
                              t = 0;  
                              if ((u = __gcd(u, n)) > 1 and u < n) return u;  
                        }  
                  }  
                  if (t and (u = __gcd(u, n)) > 1 and u < n) return u;  
            }  
      }  
      vector <long long> factorize(long long n)  
      {  
            if (n == 1) return vector <long long> ();  
            if (miller_robin(n)) return vector <long long> {n};  
            vector <long long> lchild, rchild;  
            while (n > 1 and n < MAXP)  
            {  
                  lchild.push_back(spf[n]);  
                  n /= spf[n];  
            }  
            if (n >= MAXP)  
            {  
                  long long x = pollard_rho(n);  
                  lchild = factorize(x);  
                  rchild = factorize(n / x);  
                  lchild.insert(lchild.end(), rchild.begin(), rchild.end());  
            }  
            sort(lchild.begin(), lchild.end());  
            return lchild;  
      }  
}  
   
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
   
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
   
      Rho::sieve();  
   
      int tc;  
      cin >> tc;  
      while (tc--)  
      {  
            long long a, b;  
            cin >> a >> b;  
            vector <long long> factors_a = Rho::factorize(a);  
            vector <long long> factors_b = Rho::factorize(b);  
            set <long long> st;  
            bool ok = true;  
            for (long long p : factors_a)  
            {  
                  if (st.find(p) != st.end())  
                  {  
                        ok = false;  
                        break;  
                  }  
                  st.insert(p);  
            }  
            for (long long p : factors_b)  
            {  
                  if (st.find(p) != st.end())  
                  {  
                        ok = false;  
                        break;  
                  }  
                  st.insert(p);  
            }  
            cout << (ok ? "YES" : "NO") << '\n';  
      }  
}