亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

acm求解------數格子

acm求解------數格子

翻翻過去那場雪 2018-12-07 07:56:41
將N * M個邊長為一的正方形拼成一個N* M的矩形( 每行M個小正方形,共N行 ),現在從矩形的左上角到右下角連一條線,求這條線“經過”多少個小正方形。 其中,"經過"表示該線和小正方形有無窮多個交點,即恰好過一個頂點不算??蓞⒄諛永龍D片理解 ? 第一行:T表示T組測試數據, T <= 100 接下來T行,每行N和M, N, M <= 10 ^ 4, 表示N * M個小正方形。 ? 對于每個測試數據輸出一行,一個整數R,表示經過R個正方形。
查看完整描述

1 回答

?
夢里花落0921

TA貢獻1772條經驗 獲得超6個贊

N*M(N行,M列)的矩形,內部是一個個的網格;

2*2:經過2個 ? 3*2:經過4個 4*2:經過4個

2*3:經過4個 ??3*3:經過3個 4*3:經過6個

2*4:經過4個 ??3*4:經過6個 4*4:經過4個

2*5:經過6個 ??3*5:經過7個 4*5:經過8個

不多寫了,可以發現:

1:如果M和N沒有公約數,那么經過的正方形個數就是M+N-1

? ? ?畫圖比較容易發現這一點,N*M一共含有N-1橫邊和M-1條豎邊,左上角的一個矩形是一定經過的,之后這條斜線想要進入下一個矩形,必須要經過一條內部的邊(橫邊或者豎邊),一共經過經過N-1+M-1條內部邊(因為每走一步必定經過一個邊),也就是N-1+M-1個矩形加上最左上角的一個矩形,這就是N+M-1個矩形。

2:如果M和N有公約數,那么經過的正方形個數就是M+N-(M和N的最大公約數)

? ? 其實這一點就是這條斜線經過正方形交點的情況,有多少個正方形的交點位于這條線上?是(M和N的最大公約數)-1個點,首先把這條線稍微偏移一點來避開這些交點,那么經過的矩形是M+N-1個;但是這種偏移會在每一個交點位置上添加一個經過的矩形,可以在紙上畫一下,很好理解,因為一共有(M和N的最大公約數)-1個交點,也就是多出了(M和N的最大公約數)-1個矩形。減掉這些多的矩形就可以得到實際經過的矩形數:

M+N-1-((M和N的最大公約數)-1) =?M+N-(M和N的最大公約數);

?

其實1和2可以合并起來,經過的矩形數目是:M+N-(M和N的最大公約數),問題轉換為求M和N的最大公約數,這應該就不難了。

查看完整回答
反對 回復 2018-12-16
  • 1 回答
  • 0 關注
  • 849 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號