在一個由n x m個正方形格子組成的的矩形上畫一條這矩形的對角線，這線段將穿過多少個格子？

01-06

比如在n等於m時顯然對角線上有n個格子，問題是在不相等時對角線上會有多少個格子？

為什麼像我這種從來不回答問題，也從來只看抖機靈答案，把知乎當段子集看的低逼格值賬號，居然會被人在這麼正經的問題里邀請？知乎的推薦邀請演算法是不是出了什麼問題？好吧姑且高中也是拿過奧數全國獎項的，依稀還有點記憶，我來試著解答一下，如果答錯了請偷偷告訴我，我再來想個不那麼丟臉的方式偷偷把回答刪掉。

首先從m、n互質的情況開始討論，結論是m+n-1個格子。

證明如下：因為m、n互質，除了起點和終點外，對角線不會穿過格點。而對角線在起點和終點間必然穿過m-1條豎線和n-1條橫線，這將各產生m-1和n-1個交點，因為其中沒有格點，也即交點沒有重複，所以交點總數為m-1+n-1=m+n-2個，它們把整條對角線分成m+n-1段。顯然每一段對應對角線穿過的一個格子，從而對角線穿過的格子數也為m+n-1。

接著來看m、n不互質的情況，假定它們的最大公約數為k，顯然k&>1且m/k、n/k互質。

根據上面的結果我們有m/k x n/k的矩形對角線將穿過m/k+n/k-1個格子。而m x n的矩形對角線將穿過k個m/k x n/k的矩形，也即(m/k+n/k-1)k=m+n-k個格子。

考慮到互質的兩數最大公約數為1，最後的結論是m+n-k個格子，其中k為m、n的最大公約數。

題主的m=n情況是一個特例，此時m=n=k，從而m+n-k=m=n=k。

佔個坑

考慮m n 互質時候即可

而互質的時候對應的格子數是m+n-1

手機ppi:每英寸的像素點數。

計算公式為兩邊像素數的平方和再開根號得到"像素數"。用手機尺寸(英寸)除"像素數"得到的就是ppi。明顯的對角線上的像素並不等於"像素數"。其實是任一邊的英寸除那邊上的像素數量才是正確的ppi.解決了我心中疑問:到底ppi是量對角還是邊的問題。