In the given fourth testcase, it has taken (1,1) , (2,1) , ... ,(10,1) as possible pairs, which have gcd =1, so why did you remove the case for gcd = 1?
Those are all pairs in which b = 1, so only one factor is present which is 1. For gcd = 1 i meant those pairs like (13,14), (13,16), (13,18) Because the count of pairs like these are too many in the space between 1 and m. And calculation of them would be difficult whose gcd is neither of the prime factors. Those pairs are not considered
so after reading the question my first goal was to simplify the equation since it was b * gcd(a, b) first i thought lets make that b2 and that will make the question easier first of all i eliminated gcd = 1 because that wasnt satisfying than i wrote on paper for other cases like 16, 24 gcd(16, 24) = 8 so b * gcd(16, 24) becomes 192 and a + b is 40 if you increase the value of 'a' the value of gcd(a, b) also keeps on increasing and hence we never get a suitable case for the equation i took other examples as well such as (6, 16) here b * gcd(a, b) becomes 32 and a + b = 22 so still not there and for (15, 10) here b * gcd(a, b) becomes 50 and a + b = 35 so out of the examples i made i didnt get even one suitable ans so i skipped it and since tc1 had this example 1000000 1145141 and these numbers are quite big and it worked for this so i made the conclusion that gcd != b wont be needed here
@@devanshkhandelwal5453 There is a simple proof, let's assume (a+b)%b. gcd(a,b) = 0 Then, since gcd is an integer, we can write it as b.gcd(a,b) = k.b (k is some integer) Therefore, (a+b)%k.b = 0. Then, a+b = x (k.b)= y.b (where y = x.k) (In the above step,modulo being zero implies a+b is a multiple of k.b ,thus, rewriting it like this). In the above equation, we conclude that a = l.b (l is some constant) since we should be able to take b common to make both sides of the equation identical. We get, (b.l +b) = y.b => b(l+1) = y.b , y = (l+1). Hence, we can conclude that for the inequality to hold, a should always be a multiple of b. Therefore, gcd(a.b) = b (Since gcd of any number with it's multiple is that number).
Accepted Source Code : codeforces.com/contest/1972/submission/258875633
In the given fourth testcase, it has taken (1,1) , (2,1) , ... ,(10,1) as possible pairs, which have gcd =1, so why did you remove the case for gcd = 1?
Those are all pairs in which b = 1, so only one factor is present which is 1.
For gcd = 1 i meant those pairs like (13,14), (13,16), (13,18)
Because the count of pairs like these are too many in the space between 1 and m. And calculation of them would be difficult whose gcd is neither of the prime factors.
Those pairs are not considered
@@formidablechief27 👍
Why did we assume gcd(a,b) should be equal to b. I mean, what is the proof that there will be no other answer where gcd(a,b)!=b?
so after reading the question my first goal was to simplify the equation
since it was b * gcd(a, b) first i thought lets make that b2 and that will make the question easier
first of all i eliminated gcd = 1 because that wasnt satisfying
than i wrote on paper for other cases
like 16, 24
gcd(16, 24) = 8 so b * gcd(16, 24) becomes 192 and a + b is 40
if you increase the value of 'a' the value of gcd(a, b) also keeps on increasing and hence we never get a suitable case for the equation
i took other examples as well such as (6, 16) here b * gcd(a, b) becomes 32 and a + b = 22 so still not there and for (15, 10) here b * gcd(a, b) becomes 50 and a + b = 35
so out of the examples i made i didnt get even one suitable ans so i skipped it
and since tc1 had this example 1000000 1145141 and these numbers are quite big and it worked for this so i made the conclusion that gcd != b wont be needed here
@@formidablechief27 Ok, got it. Thanks!
@@devanshkhandelwal5453 There is a simple proof, let's assume (a+b)%b. gcd(a,b) = 0
Then, since gcd is an integer, we can write it as b.gcd(a,b) = k.b (k is some integer)
Therefore, (a+b)%k.b = 0.
Then, a+b = x (k.b)= y.b (where y = x.k) (In the above step,modulo being zero implies a+b is a multiple of k.b ,thus, rewriting it like this).
In the above equation, we conclude that a = l.b (l is some constant) since we should be able to take b common to make both sides of the equation identical.
We get, (b.l +b) = y.b => b(l+1) = y.b , y = (l+1). Hence, we can conclude that for the inequality to hold, a should always be a multiple of b.
Therefore, gcd(a.b) = b (Since gcd of any number with it's multiple is that number).