### 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.