Please somebody solve it using 1- based indices.
I am not able to understand the last part, that how come answer for no of matches become g + 1. I got the same equation given in editorial, but at the end how come this happens --> i = lp and j = lq and from this how do we draw conclusion that g + 1 is no of matches in both the matrices.
Please Help!
Just a note: in editorial are used 0-based indexes, while in problem statement there wer 1-based indexes used…
for n=1 or m=1 shouldnt the answer be just max(n,m) ?
1 Like
for n=1,m=1 obviously answer is 1 only.
You can do it like: if(n==1 && m==1) ans=1 else ans=gcd(n-1,m-1)+1
I hope you’ll not mind that I’ve edited the post, but there was an obvious mistake in the boundary case.
1 Like
you do not need to check if(n==1 && m==1) because you have gcd(0,0) will return 0
Strangely (to me), the GCD needed to have variables a and b defined as long (instead of int) to work:
static long GCD(long a, long b)
{
if (b == 0) return a;
return GCD(b, a % b);
}
Thus, I defined cnt2 as a long also. It does not seem to me that a, b, a%b, or GCD(a,b) would ever be greater than an int value.
when “if (n == 1 || m == 1)” comes out true then output should be 1.
Manal, I think you mean “if (n==1 && m==1)” then output should be 1. Otherwise, if n==1 or m==1 then the answer would be the other number (e.g. n=1, m=5, then output 5).
may be the problem was elsewhere, because everyones solution used 32 bit numbers only
1 Like
going by strict definition of divisors, gcd(0, i)should be undefined. However, people conveniently extend it to mean that gcd(i, 0) = i.
@utkarsh_lath [Not something relating to this problem] I remember a problem from some previous contest, where 0^0 was conveniently taken as 1. That didn’t go by strict definitions.
Its all about conventions and widely accepted norms. Whether 0^0 is 0 or 1 is usually clear from the context.
Sometimes people give special mention to such things, sometimes assume that others are aware of it.
1 Like
0 based indexes makes reasoning much easier to convey / come up with.
1 Like
@utkarsh_lath Can you explain how gcd(0,i) should be undefined ? One way of looking at it could be that lcm(0,i) is 0 and so gcd(0,i) = (0*i)/0. How can we fundamentally prove it ?
What was the test case that caused my original program (using int) to fail, which did pass my modified program (using long)? I directed the question via e-mail to contest-admin, but the response was to post the question here in the editorial.
His solution looks straight-forward and ok, though, I’m puzzled by this difference as well:
http://www.codechef.com/viewsolution/2706599
I solved it by making the above equation.It is called a linear Diophantine equation and its solution can be found easily on google