OPTPAIRS Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Lavish Gupta
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

1666

PREREQUISITES:

None

PROBLEM:

For two positive integers a and b, let g(a, b) = gcd
(a, b) + lcm(a, b).

For a positive integer N, let f(N) denote the minimum value of g(a, b) over all the pairs of positive integers (a, b) such that a+b = N.

Find out the number of ordered pairs (a, b) such that a+b = N and g(a, b) = f(N).

EXPLANATION:

Observation 1: For all 1 \leq a \leq N, which are factors of N,

gcd(N-a,a) = a

Proof:
By the property

gcd(A,B) = gcd(A-B,B)

We can write

gcd(N-a,a) = gcd(N-2a,a) = gcd(N-(\frac{N}{a} - 1)a) = gcd(a,a) = a

Also using the property

gcd(a,b) \times lcm(a,b) = a \times b

we get,

g(a,N-a) = a + \frac{a \times (N-a)}{a} = N

which is the minimum value we can get. To prove this let us assume a is not a factor of N.
Then g(a,N-a) = gcd(a,N-a) + \frac{a(N-a)}{gcd(a,N-a)}.
Let us assume:

L = N - g(a,N-a) \\ L = N - gcd(a,N-a) - \frac{a(N-a)}{gcd(a,N-a)}

Simplifying it we get

L = (1 - \frac{a}{gcd(a,N-a)})((N-a) - gcd(a,N-a))

Since gcd(a,b) \leq min(a,b), therefore we can see that the first term of L will always be \leq 0 while the second term will always be \geq 0, so we conclude that

L \leq 0 =\gt N \leq g(a,N-a)

Thus we can select all possible factors of N as a and b would be (N-a). This way we can find all possible pairs (a,b) that gives minimum value of g(a,b).

TIME COMPLEXITY:

O(\sqrt{N}), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2 Likes
2

The proof was really difficult

10 Likes
3

Alternate approach (with less maths)-

  1. Let’s take test case 2, N=105 and observe some patterns.
    We can break it into 1 + 104 and it will have GCD=1, LCM=104 and their sum as 105, for each N, A=1, B= N-1 will be the minimum value that we can have for LCM+GCD
  2. Tabulate A from 104-1 and B from 1-104 in excel and calculate GCD, LCM for some hint
    |a|b|gcd|lcm|sum|
    |—|—|—|—|—|
    |1|104|1|104|105|
    |3|102|3|102|105|
    |5|100|5|100|105|
    |7|98|7|98|105|
    |15|90|15|90|105|
    |21|84|21|84|105|
    |35|70|35|70|105|
    |70|35|35|70|105|
    |84|21|21|84|105|
    |90|15|15|90|105|
    |98|7|7|98|105|
    |100|5|5|100|105|
    |102|3|3|102|105|
    |104|1|1|104|105|

we see that for A= 1,3,5,7,15,21,35 we get sum of GCD and LCM as 105
After that higher values of A are inversion of same.

  1. One insight can be drawn from this is that 3,5,7 are prime factors of 105, and 15,21,35 are their products. So we get minimum values for prime factors of 105 (and their products) as they divide it in whole way.
    ** also think about it, this problem basically is- number of ways to divide a number N in two parts such that one part divides other in whole**

  2. So if we find prime factors and their frequencies, exclude that one case where all prime factors are taken (3 x 5 x 7 is 105 we cant have that as A because then B will be zero) we can calculate our answer by counting distinct values that A can have(with prime factors and their repetition) times 2 (since we are looking for A=1- 35 only in this case or half of the ordered pairs)

Solution Link (java) - CodeChef: Practical coding for everyone

PS- Too much maths involved and it wasn’t a problem that would have 1800+ submission in no time. (ideal problem to spot plagiarism)

3 Likes
4

There’s a simpler proof i think, let two numbers be a and N-a, Assume, a<=N-a. Now, if a is a divisor of N, then N=k * a, for some k. So N-a = a*(k-1). So gcd(a, N-a) = a, and LCM(a, N-a) = N-a (as N-a itself is a multiple of a). So gcd + lcm = N.

If a is not a divisor of N, then, LCM(a, N-a) can’t be N-a, because, N-a can’t be a multiple of a. Since LCM has to be multiple of N-a, and it can’t be N-a, so LCM >=2*(N-a) (the next multiple of N-a), however, we assumed a<=N-a, which means, N-a>=ceil(N/2), which means LCM>=N.

So gcd + lcm >=N (if a is not a multiple of N). So, we’re done! Yay!

13 Likes
5

Proof by AM-GM Inequality:
Since a and b are positive, therefore from AM-GM
2sqrt(ab)<=(a+b)
or 2sqrt(ab)<=N —eqn 1

Since lcm and gcd of (a,b) are also positive, again applying AM-GM
lcm(a,b)+gcd(a,b)>=2sqrt(ab) —eqn2

If we insert the maximum value of 2*sqrt(a,b) from eq1, then also eqn2 should satisfy. Therefore,
lcm(a,b)+gcd(a,b)>=N.

3 Likes
8

That’s now how inequality works bro. For merging two different inequalities the sign must be same.

This does not make any sense. Take a smaller value of 2*sqrt(a,b) = N-1 and put it in eq2 then you’ll get lcm+gcd >= N-1 .

9

hie bro. can u plz explain this problem to me? can u plz share ur discord id?

10

I am not merging the 2 inequalities. I am just saying that the value greater than the maximum value is always greater. Example:
a+b>c
c<10
Then we can always write a+b>=10 or a+b>=11 or a+b>=12, because all the value are greater than 10 which is the maximum value of c.

We cannot replace with smaller value because the value can be greater.

1 Like
11

me who thought it as ok given constraint is 10^9 so the time complexity may be less than or equal to O(squareroot(n)) so as it belongs to math problem we know it take O(squareroot(n)) to find all divisors of a number so they might the pairs we need to thought off
i know its not the correct way to solve the problem but its ok to guess based on constraints some times :grinning: :grinning: :grinning: :grinning:

12

ok

13

Simple and clear!

14

Indeed! I could not solve the problem and there were already 1000+ submission so I check on you tube and there were 900+ views on solution video. That is just disgusting🤬.

15

How did u simplify? shouldn’t it be L-a <= 0?

16

https://www.codechef.com/viewsolution/66951122

17

I think you should prove N < g(a,N−a) when a is not a factor of N, otherwise there could be non-factors reaching the minimum value. Am I missing anything?