ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - e565: 10407 - Simple division　解題心得

Not In My Back Yard | 2019-12-16 21:49:26 | 巴幣 12 | 人氣 375
題目連結：
題目大意：
輸入有多筆測試資料，每筆佔一列（當某一列只包含一個 0 代表輸入結束）。每列給定不定量的整數（以 0 作為數列的結尾），數列的長度至少 2 但不超過 1000 ，且所以數字彼此相異。

請求出最大的正整數 d ，使得數列當中所有數字除以 d 的餘數（如果被除數是負數，則餘數應要取正數）皆相同。

範例輸入：
701 1059 1417 2312 0
14 23 17 32 122 0
14 -22 17 -31 -124 0
0
範例輸出：
179
3
3
解題思維：
假設數列 A1 、 A2 、 …… 、 An ，各自除以 d 後得到的商數為 Q1 、 Q2 、 …… 、 Qn 且都得到相同的餘數 R 。則數列可重寫為 Q1 × d ＋ R、 Q2 × d ＋ R、 …… 、 Qn × d ＋ R 。

接著取相鄰兩項的差值：
(Q1 － Q2) × d 、 (Q2 － Q3) × d 、 …… 、 (Qn-1 － Qn) × d
可以看出，此時的正整數 d 是所有差值的共同因數。因此，要將 d 最大化，即是要求這些差值的最大公因數。

因此，
GCD(A1 － A2, A2 － A3, ……, An-1 － An)  ＝
GCD(……GCD(GCD(A1 － A2, A2 － A3), A3 － A4), ……), An-1 － An)
即為所求。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
追蹤 創作集

作者相關創作

相關創作

更多創作