The Game Is Back On

Pre-requisite: Sieve of Eratosthenes

Given two numbers A and B, we get the following -

A ***** B = LCM(A,B) ***** GCD(A,B)

Now, if A and B are co-prime, then GCD(A,B) = 1. Therefore,

A ***** B = LCM(A,B)

Imagine, N has a prime factor p, and it appears k times in N. Now, because GCD(A,B) = 1 and AB = LCM(A,B), p will appear k times in either A or B (otherwise AB will not be N), but never in both of them (because then they wouldn't be co-prime). So if N has x prime factors, basically what we have to do is divide the primes into two different sets. And the number of ways we can do this is 2(x-1). The answer is 2(x-1) instead of 2x because (A,B) and (B,A) are counted as the same pair. If you have any confusion, read this to understand how the formula for counting subset is derived.

We will be using Sieve of Eratosthenes to find all the prime numbers below 106. We will check against each of these prime if N is a multiple of that prime. Note that, since N can be as large as 1012, N can have at most one prime factor bigger than sqrt(N) (in this case, 106). So after dividing N by all the primes below 106 as many times as possible, if N is still larger than 1, then N has a prime factor bigger than 106.

C++ code:

#include <bits/stdc++.h>

using namespace std;

#define MAXA 1000000


int main()
{  
    bool prime[MAXA+6];
    std::vector<long long> v;

    memset(prime,0,sizeof(prime));

    //implementing sieve
    for(int i = 4; i <= MAXA; i += 2) prime[i] = 1;

    for(int i = 3; i*i <= MAXA; i += 2)
    {
        for(int j = i*i; j <= MAXA; j += i+i) prime[j] = 1;
    }

    v.push_back(2);
    for(int i = 3; i <= MAXA; i += 2) 
        if(!prime[i]) v.push_back(i);

    //now we have all the primes below 10^6 in v

    int t;
    cin >> t;

    while(t--)
    {
        int ans, ct = 0;
        long long n;

        cin >> n;

        ct = 0;

        for(int i = 0; i < v.size(); i++)
        {
            if(v[i] > n) break;

            if(n % v[i] == 0)
            {
                ct++;
                while(n % v[i] == 0) n /= v[i];
            }
        }

        if(n > 1) ct++; //n has a prime factor bigger than 10^6

        ans = 1;

        for(int i = 1; i < ct; i++) ans *= 2;

        cout << ans << endl;
    }

    return 0;
}