[Codeforces] E. Divisor Paths

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Divisor Paths
Source            : Codeforces 
Category          : Number Theory
Algorithm         : Pollard Rho Prime Factorization
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 2e5 + 5;  
static const long long mod = 998244353LL;  
  
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;  
      }  
}  
  
long long binary_expo(long long a, long long p, long long m = mod)  
{  
      if (p == 0) return 1 % m;  
      if (p == 1) return a % m;  
      if (p & 1) return (a % m * binary_expo(a, p - 1, m)) % m;  
      long long ret = binary_expo(a, p >> 1, m);  
      return (ret % m * ret % m) % m;  
}  
  
long long mod_inv(long long a, long long m = mod)  
{  
      return binary_expo(a, m - 2, m);  
}  
  
long long fact[105];  
long long ifact[105];  
  
void preCalc()  
{  
      fact[0] = 1;  
      ifact[0] = 1;  
      for (int i = 1; i < 105; i++)  
      {  
            fact[i] = (1LL * i * fact[i - 1]) % mod;  
            ifact[i] = mod_inv(fact[i]);  
      }  
}  
  
vector <long long> factors;  
  
long long ways(long long n)  
{  
      int total = 0;  
      long long ret = 1;  
      for (long long pf : factors)  
      {  
            int cnt = 0;  
            while (n % pf == 0) cnt++, n /= pf;  
            ret = (ret * ifact[cnt]) % mod;  
            total += cnt;  
      }  
      ret = (ret * fact[total]) % mod;  
      return ret;  
}  
  
  
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  
  
      preCalc();  
      Rho::sieve();  
  
      long long d;  
      cin >> d;  
      factors = Rho::factorize(d);  
      sort(factors.begin(), factors.end());  
      factors.erase(unique(factors.begin(), factors.end()), factors.end());  
      int q;  
      cin >> q;  
      while (q--)  
      {  
            long long u, v;  
            cin >> u >> v;  
            long long g = __gcd(u, v);  
            long long ans = (ways(u / g) * ways(v / g)) % mod;  
            cout << ans << '\n';  
      }  
}