Last Updated: 23 Apr, 2022
A Number Game
Moderate
Asked in company
Ninja has an integer 'A'.
He will go through all integers 'X' from 1 to 10^18 and for every 'X', he will store the value of 'LCM(X,A) ÷ X'.
He wants to know the number of unique values he will obtain in the end.
Example :
‘A’ = '2'
For X = 1, Ninja will get LCM(1,2) ÷ 1 = 2/1 = 2.
For X = 2, Ninja will get LCM (2,2) ÷ 2 = 2/2 = 1.
For X = 3, Ninja will get LCM (3,2) ÷ 3 = 6/3 = 2.
For X = 4, Ninja will get LCM (4,2) ÷ 4 = 4/2 = 2.
For X = 5, Ninja will get LCM (5,2) ÷ 5 = 10/2 = 2.
For X = 6, Ninja will get LCM (6,2) ÷ 6 = 6/6 = 1.
And so on, It can be verified that Ninja will never get any integer other than 1 and 2. Hence the answer for 'A' = 2 is 2.
Input Format :
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains a single integer 'A'.
Output format :
For each test case, output the number of unique integers obtained for the function provided in the problem statement.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 ≤ T ≤ 10
0 ≤ A ≤ 10^10
Time Limit: 1 sec
Approaches
Approach :
- For two (positive) integers 'X' and 'A', the properties of their greatest common divisor gcd and the least common multiple lcm come in pairs; the phenomenon is partly explained by the formula 'GCD(X, A)' × 'LCM(X, A)' = 'X' × 'A'.
- Rearranging, 'LCM(X,A) ÷ X' = 'A ÷ GCD(X,A)'.
- 'GCD(X,A)' can have minimum value of 1, so the maximum value of the equation will be 'A'.
- 'GCD(X,A)' can have a maximum value 'A' (as 'A' <= 10^18), hence the minimum value of the equation will be 'A ÷A' = 1.
- Now, for all values of 'X', 'GCD(X,A)' are either divisors of 'A' or multiples of divisors of ‘A’. Hence the unique integers than can be obtained is simply the number of divisors of 'A'. So the problem boils down to finding the number of divisors of 'A'.
Algorithm:
- Initialize an integer variable 'count' to store the number of divisors of 'A'.
- Iterate using variable 'i' from '1' to 'i * i' <= 'A'.
- if('i' * 'i' == 'A'), we increment our 'count' by '1' since both the factors of the pair ('i' and 'A/i') are same.
- Otherwise if ( 'A%i' == 0 ), we increment our 'count' by 2, since both the factors ('i' and 'A/i') are distinct.
- Return 'count'.