RRMATRIX - Editorial

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:

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

CodeChef: Practical coding for everyone (int)

CodeChef: Practical coding for everyone (long)

I’m failed to proceed further

I am also not able to solve further…

general solution of ax+by=c:
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

here are the links:

CodeChef: Practical coding for everyone (int)

CodeChef: Practical coding for everyone (long)

@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