PROBLEM LINK:
Author: Vineet Shah
Editorialist: Vaibhav Jain
DIFFICULTY:
MEDIUM
PREREQUISITES:
Primality Test, Sieve of Eratosthenes
PROBLEM:
Find the number of ordered pairs (b,c) such that it satisfies the following equation:
a+(b×c)=a×b+a×c
QUICK EXPLANATION:
We can rewrite equation as a(a-1)=(b-a)(c-a). Now the answer will be 2×fact(a)×fact(a-1) where fact(i) is the number of factors of i.
EXPLANATION:
Let us consider our equation:
a+(b×c)=a×b+a×c\tag*{}
Rewrite it as:
a+b×c-a×b-a×c=0\tag*{}
Adding a^{2} both sides:
a+b×c-a×b-a×c+a^{2}=a^{2}\tag*{}
Taking common:
b×(c-a)+a×(a-c)=a^{2}-a\tag*{}
Rearranging:
(b-a)×(c-a)=a×(a-1)\tag*{}
Now we can see that number of ordered pairs (b,c) shall be equal to the factors of a×(a-1) i.e. fact(a)×fact(a-1). This is because fact(a) is multiplicative function and gcd(a,a-1)=1. Note here that if (b,c) satisfies equation so does (-b,-c) and similarly when (b,-c) satisfies equation so does (-b,c). Hence, actual answer will be 2×fact(a)×fact(a-1). But finding factors of a will give TLE. Hence we will use concept here.
We can precompute every prime number till 10^{6} using the old Sieve of Eratosthenes or whatever variant you prefer. Now we will divide a from every prime factor till 10^{6} to count the powers of distinct prime numbers to calculate number of factors. After doing this a must be either 1 or if not then a must have prime factor(s) greater than 10^{6}. Claim: In this case a can have either only one or two prime factors greater than 10^{6}. This is because if a will have three prime factors greater than 10^{6} it will exceed 10^{18}. Hence, to check whether a has only factor or two factors left can be done using primality test.
If primality test comes out to be true that means a has left only one factor otherwise it has two factors. For large numbers we will use one of the probabilistic methods of primality test whose complexity is O(klogn) where k is number of iterations.
Now only a=0 and a=1 will output -1. This is because 0 has infinite factors which means infinite pairs.
Those who don’t know how to find number of factors of large numbers can try problem given in Related Problems.
EDITORIALIST’S SOLUTIONS:
Editorialist solution can be found here.