SWAPSIGN(Code Melange) - EDITORIAL (UNOFFICIAL)

PROBLEM LINK:

Practice
Contest

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.

RELATED PROBLEMS:

https://www.codechef.com/PRACTICE/problems/NUMFACT

1 Like

Mention this as well -
Let fact(x) = no of factors of x.
And fact(x) is a multiplicative function.
Because gcd(a,a-1) is 1.
Therefore, fact(a*(a-1)) = fact(a)*fact(a-1).

2 Likes