I have correctly performed all tests from the forum, but still WA 3. Please tell me what the problem is or write new tests for me.

check the values ​​of y[i] by x[i] - x[i-1] in the straight line equation
>
>
>
>
>
>
>
>
use ceil() and floor()

https://math.stackexchange.com/questions/2138051/how-many-squares-is-passing-the-diagonal

Edited by author 16.09.2020 22:50

What is test 8?
What input ?

Edited by author 13.11.2009 15:02

Edited by author 13.11.2009 15:02

//pseudo code
divider = first_input-1;
dividend = second_input-1;
result: divider + dividend - FindCrossesOnTheWay(dividend,divider)
*FindCrossesOnTheWay
if(divider < dividend) swap()
for(i=1;i<=divider;i++)
if((dividend * i) % divider == 0) crosses++

Well, this is for those who didnt get the method.
Consider N: no of rows of blocks M: no of columns of the blocks (N+1 and M+1 are the input).
Crosspoint here refers to a point where a horizontal and a vertical line meet.

For each line that the plane intersects, a new block is introduced. Consider the south western most point also as one such point. No of horizontal lines intersected=N. No of vertical lines intersected=M. But the southwestern most point has been counted twice and it introduces the same first block.
If gcd(M,N)==1, there is no intermediate point where the line passes over a crosspoint. Hence no. of blocks = M+N-1.
If gcd(M,N)!=1, the whole grid can be split horizontally at
the points where the line passes over a crosspoint and each of them can be considered separately with that cross point as the south westernmost point of the subproblem. There are gcd(M,N) such points. Say a=gcd(M,N). Then in each subproblem  the line flies over M/a+N/a-1 blocks. Totally the line flies over a*(M/a+N/a-1) blocks. ie. M+N-a blocks.

Edited by author 29.11.2007 02:42

I wrote simple implementation but can't figure out test to prove my solution wrong.

4 3 -> 4
3 3 -> 2
4 5 -> 6
4 6 -> 7
3 8 -> 8
6 5 -> 8
6 8 -> 10

#include "stdio.h"
#include <stdlib.h>

int main(void) {
  int bigger, lesser, a, b;
  scanf("%d", &a);
  scanf("%d", &b);
  if (a >= b) {
    bigger = a - 1; lesser = b - 1;
  } else {
    bigger = b - 1; lesser = a - 1;
  }

  if (bigger % lesser == 0) {
    printf("%d\n", bigger); return 0;
  }

  printf("%d\n", bigger + lesser - 1);

  return 0;
}

For each x (x=0,1,2,..,n-1) (x is horizontal axis)  find y0=x*tg(a) and y1=(x+1)*tg(a),  where tg(a) is (m-1)/(n-1).  Add to answer floor (y1) - floor(y0) +1. If y1 is a whole number then subtract 1 from answer.

If the plane fly across a edge and it will produce a point then produce a new block so the answer add one.
If gcd(M, N) = 1, it means there is no situation that the plane fly across the crossroads.
See from left to right it produce M point and see from north to south it produce N point,
but one is calculate twice, so there are M + N - 1 points and Ans is M + N - 1.

i used bresenham line drawing algorithm :)) together with gcd()

I use Python 3.5
Is it right that it's prohibited to import function gcd from library math?
But it's allowed to import this function from library fractions

Edited by author 27.11.2015 02:04

for input 3 3, I guess the result should be 3. Why it is 2?

Does anybody know what is test #3?

For whom who use floating K = n / m, try to this test:
3 99  - right answer is 98
99 3  - right answer is 98

4 3 - 4
3 3 - 2

Is it not true 4 3 - 6, 3 3 - 3?