What if I start calculating from 1- based index. e.g. A(i,j) = (i-1) * M + j and B(i, j) = (j-1) * N + i then by equating these two, I get i(M-1)-M= j(N-1)-N ; How to proceed further?
@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
@utkarsh_lath No, gcd(i,0) really is i (for i>0), as i divides both i and 0 and no greater number does. Iām guessing youāre thinking of 0 dividing i instead of i dividing 0?
Doesnāt change the fact that the editorial makes false statements. If you want to make an index shift, say so.
problem is probably system related, in those two submissions, there is only change from int to long
Iām failed to proceed further
I am also not able to solve furtherā¦
Please somebody solve it using 1- based indices.
general solution of ax+by=c:
x=x1-t*(b/g)
y=y1+t*(a/g)
where t=constant and g=gcd(a,b)
x1 and y1 is intial solution
In this question,x1=1 and y1=1
and final solution x2=n-1 and y2=m-1
use this equation to find the value of t which gives the number of solutions.
You have not given link to your solution
@betlista, @dwoolley3, @stefanpochmann It is some compiler related issue. The int program shows WA for test file 0, when I download it and run on my system, the output is exactly as expected. I have never used C#, so I cant comment on this much.
@stefanpochmann: If the line
0 ā¤ i < N, 0 ā¤ j < M
were missing, I would gladly accept what you just said. However, the above line makes it perfectly clear that we are using different indices subsequently. Things need not be stated twice. If you plan to skip reading some of the lines, you can end up missing some facts.
I looked up the definition of gcd, and it showed that you people are right. gcd(a,b) is defined if at least one out of a and b is non zero.
I was thinking along the lines that i is not a factor of 0, so gcd(i,0) cannot be i.
you can write the above as
i * (M-1) - (M - 1) = j * (N-1) - (N -1)
(i-1) * (M-1) = (j-1) * (N-1)
Then proceed along the lines of solution given in editorial.
1 Like
Thatās not the same as really saying it, and itās poor style.
Here is the link to the 3rd submission during the contest, which was deemed wrong (but becomes right by changing the int to long for GCD method): http://www.codechef.com/viewsolution/2705928