Lightoj 1236 - Pairs Forming LCM

The problem statement actually refers to finding out number of pairs of integers that have LCM n ( which is the given value). There can be 2000 test cases and value of n can be at most 10¹⁴.
let's assume that the prime factorization of n can be represented as
n = p1^q1.p2^q2.......px^qx , where p1,p2....px are prime numbers and q1,q2...qx are corresponding powers.

lets assume that any two integers are i and j such that LCM(i,j)=n. since n is their LCM, the prime factorization of i and j must have the following qualities.

1. if i = px^qx then j must be either j = px^qx-1 or j = px^qx-2 or ..... j = px⁰
2. if j = px^qx then i must be either i = px^qx-1 or i = px^qx-2 or ..... i = px⁰
3. i = px^qx and j = px^qx

for the 1st scenario we can see there are qx combinations
for the 2nd scenario we can see there are qx combinations
for the 3rd scenario we can see there are 1 combinations

so, there can be a total of 2*qx + 1 combinations for each of the prime factors of n. since all the prime factors are independent we get the answer-

ans = (2*q1 + 1) * (2*q2 + 1) * ..........(2*qx + 1)

but the problems says i<=j for any combinations. if LCM of 12 is given we can take (3,4) as a pair but can't take (4,3). since, Our answer contains all the possibilities without considering orders it is calculating all the combinations twice actually. there's one exception which is (n,n). so, we have to divide our answer in half and add one for the exception pair. ans = (ans/2)+1; Here is the source code..

#include<bits/stdc++.h>
///...................................*****.................................................///
///        Author :  Raihan Khan Raka  ( raihankhanraka@gmail.com )                         ///
///                  Department of Computer Science                                         ///
///                  & Engineering                                                          ///
///                  Comilla University , Bangladesh.                                       ///
///...................................*****.................................................///

/*....................................Values................................................*/
#define       p5                   100007
#define       p6                   1000007
#define       PI                   acos(-1)
#define       M                    1000000007
#define       inf                  1LL << 62
#define       white                0
#define       gray                 1
#define       black                2
/*....................................Functions.............................................*/
#define       sqr(x)               x*x
#define       sc                   scanf
#define       pf                   printf
#define       pfn                  printf("\n")
#define       scin(x)              sc("%d",&(x))
#define       scin2(xx,zz)         scanf("%d %d",&xx,&zz)
#define       scln(x)              sc("%lld",&(x))
#define       scln2(xx,zz)         scanf("%lld %lld",&xx,&zz)
#define       min3(a,b,c)          min(a,b<c?b:c)
#define       max3(a,b,c)          max(a,b>c?b:c)
#define       all(v)               v.begin(), v.end()
#define       ok                   cout << "ok" << endl
#define       mem(x,y)             memset(x,y,sizeof(x))
#define       clr(a)               a.clear()
#define       READ(f)              freopen(f, "r", stdin)
#define       WRITE(f)             freopen(f, "w", stdout)

/*...................................Data_Types............................................*/
#define       lli                  long long int
#define       ull                  unsigned long long int
#define       pii                  pair < int, int>
#define       pll                  pair < ll, ll>
#define       veci                 vector<int>
#define       vecl                 vector<long long int>
#define       vecp                 vector<  pair<int,int> >
#define       mapstrint            map< string , int >
#define       mapstrstr            map< string , string >
#define       mapint               map< int, int >
#define       uset                 unordered_set
#define       umap                 unordered_map
#define       pq                   priority_queue

#define       pb                   push_back
#define       mp                   make_pair
#define       ff                   first
#define       ss                   second

/*.....................................Loops...............................................*/
#define       rep( i , a , b )     for( i=a ; i<b ; i++)
#define       rev( i , a , b )     for( i=a ; i>=b ; i--)
#define       repx( i ,a,b, x)     for( i=a ; i<b ; i+=x)

#define       IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);


//int month[]={31,28,31,30,31,30,31,31,30,31,30,31};
//long power(long int x, long int y){ int temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp; }
/*lli gcd(lli x,lli y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}
lli bigmod(lli n, lli k)
{
    lli ans=1;
    while(k)
    {
        if(k&1)
            ans=(ans*n)%M;
        k=k>>1;
        n=(n*n)%M;
    }

    return ans;
}
*/
/*
int dx4[5] = {1, -1, 0, 0 };
int dy4[5] = {0, 0, 1, -1};
int dx8[9] = { 0 , 0 , -1 , 1 , -1 , -1 , 1 , 1 } ;
int dy8[9] = { -1 , 1 , 0 , 0 , -1 , 1 , -1 , 1 } ;

int knightx[9] = { -1 , 1 , -2 , 2 , -2 , 2 , -1 , 1 } ;
int knighty[9] = { -2 , -2 , -1 , -1 , 1 , 1 , 2 , 2 } ;

bool valid( int r , int c , int x , int y ){ if( x >= 1 && x <= r && y >= 1 && y <= c ) return 1 ; return 0 ; }
*/

using namespace std;
bool vis[110*p5];
vecl v;

void seive(lli n)
{
    lli root=sqrt(n)+1,i,p,j;

    v.pb(2);
    vis[0]=vis[1]=1;
    for(i=3;i<=root;i+=2)
    {
        if(!vis[i])
        {
            v.pb(i);
            p=i<<1;
            for(j=i*i;j<=n;j+=p)
            {
                vis[j]=1;
            }
        }
    }

    for(i=root&1?root+2:root+1;i<=n;i+=2)
    {
        if(!vis[i])
            v.pb(i);
    }
}
int main()
{
   lli t,i,j,k,p,ans,n;
   seive(10000007);
   k=v.size();

   scln(t);

   rep(i , 1, t+1)
   {
       scln(n);
       ans=1;
       for(j=0;v[j]*v[j]<=n and j<k;j++)
       {
           if(n%v[j]==0)
           {
               p=0;
               while(n%v[j]==0)
               {
                   p++;
                   n/=v[j];
               }
               ans*=((2*p)+1);
           }
       }

       if(n>1)
        ans*=3;   // 2*1+1

       ans>>=1;
       ans++;

       pf("Case %lld: %lld\n",i,ans);
   }

#ifdef HOME
    cerr << "Time elapsed: " << clock() / 1000 << " ms" << endl;
#endif
    return 0;
}