ALGO NOTEBOOK

Euler's Totient Function Euler's Totient function returns the number of positive integers less than or equal to n which are co-prime with n. Two numbers are co-prime when they have no common divisors or their gcd is 1. For instance,  phi(8)=4  , since there's four integers 1,3,5,7 that are co-prime with 8. Prime numbers are co-prime with any number below it. if P is a prime number then  phi(P)=P-1  . For instance  phi(7)=6  , since 1,2,3,4,5,6 all are co-prime with 7. Phi function is also multiplicative. That means if n=a*b , then, Phi(n) = Phi(a * b) = Phi(a) * Phi(b) if a and b are not relatively co-prime then Phi(n) = Phi(a * b) = Phi(a) * Phi(b) * d/phi(d) , where d=gcd(a,b) P1 and P2 are prime numbers and n can be represented in the form of n=P1*P2, then Phi(n) = Phi(P1 * P2) = Phi(P1) * Phi(P2) = (P1-1) * (P2-1)  for instance , 21 = 3 * 7 Phi(21)=Phi(3) * Phi(7) =(3-1) * (7-1) ...

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 14 . 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 0 2. if j = px qx then i must be either i = px qx-1 or i = px qx-2 or ..... i = px 0 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 pr...