d****2
发帖数: 109 | 1 A n*m rectangular, draw one line connect two opposite vertex, e,g, (1,1) - (
n,m), how many small squares the
line will cross (cross means the line will be in the square, not on the edge
). | a**m
发帖数: 102 | 2 m+n-gcd(m,n)?
(
edge
【在 d****2 的大作中提到】
: A n*m rectangular, draw one line connect two opposite vertex, e,g, (1,1) - (
: n,m), how many small squares the
: line will cross (cross means the line will be in the square, not on the edge
: ).
| t******y
发帖数: 1100 | 3 yes
【在 a**m 的大作中提到】
: m+n-gcd(m,n)?
:
: (
: edge
| d****2
发帖数: 109 | 4 cool, how did you get it?
【在 a**m 的大作中提到】
: m+n-gcd(m,n)?
:
: (
: edge
| r*******s
发帖数: 303 | | a**m
发帖数: 102 | 6 first consider the case that gcd(m,n)=1:
Suppose n>=m, consider the intersections of the diagonal and the horizontal
lines, their coordinates are 0, m/n, 2m/n, ...,nm/n(=m).
if the open interval ((k-1)m/n, km/n) contains an integer, this means the
diagonal crosses 2 squares in the k-th row, otherwise it crosses only 1
square.
Note that the open interval can contain as many as one integer because n>=m.
We know that 1,2,...,m-1 will appear in some of the n open intervals, so
there are m-1 open int
【在 d****2 的大作中提到】
: cool, how did you get it?
| p*****k
发帖数: 318 | 7 note the problem asks (1,1) instead of (0,0)
a simple fix though | d****2
发帖数: 109 | 8 good, thanks
horizontal
m.
contains
【在 a**m 的大作中提到】
: first consider the case that gcd(m,n)=1:
: Suppose n>=m, consider the intersections of the diagonal and the horizontal
: lines, their coordinates are 0, m/n, 2m/n, ...,nm/n(=m).
: if the open interval ((k-1)m/n, km/n) contains an integer, this means the
: diagonal crosses 2 squares in the k-th row, otherwise it crosses only 1
: square.
: Note that the open interval can contain as many as one integer because n>=m.
: We know that 1,2,...,m-1 will appear in some of the n open intervals, so
: there are m-1 open int
| l******i
发帖数: 1404 | 9
惊见系里大师兄
【在 t******y 的大作中提到】
: yes
|
|
