Problem Link:
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)