TWOFUN - Editorial

Practice
Contest

Author: murugappan_s
Testers: sdssudhu,msv99999
Editorialist: murugappan_s

DIFFICULTY: Easy

PREREQUISITES: Math

PROBLEM:
Given two integers A and B, in which one of them is guaranteed to be equal to 2 . With A and B, you are allowed to create any number X which can be expressed as M∗A+N∗B for any non-negative integers M and N.

Find out the number of natural numbers which cannot be expressed as stated above. If there are infinite of them then print −1.

CONSTRAINTS:
1 ≤ A,B ≤ 100000

SOLUTION:

Claim 1:
`All even numbers can be expressed as stated M*A+N*B.`
Proof:
One of the number amongst A and B is guaranteed to be equal to 2(lets assume it to be A), so with M*2+B*0 we can generate all even numbers.

Claim 2:
`If both A and B are even, then no odd number can be generated.`
Proof:

• Multiples of even numbers are guaranteed to be even. So M*A and N*B are even.
• Sum of two even numbers is even. So M*A + N*B is even.
• Which implies none of the odd number can be generated, therefore the answer is infinite.
• Additional fact: If M*A+N*B=K then gcd(A,B) | K, that’s why sum of two even numbers is always even.

Claim 3:
`Lets assume A to be 2 and B to be an odd number. Any odd number greater than or equal to B can be generated.`
Proof:
We have B with us initially. The next odd number B+2 can be generated by adding A=2 to B. Generalizing it we get, M*2 + B*1 which generates all odd numbers greater than or equal to B(B,B+2,B+4,B+6,........B+2*M). So the smallest odd number that can be generated is B.

Combining claims 1 and 2, we can generate all even numbers and all odd numbers greater than or equal to B(given A=2 and B is odd). So what is left are the odd numbers lesser than B, their count equals floor(B/2) or (B-1)/2.

Time Complexity: O(1)