#41974: 簡單的找規律
s10900156@nhsh.tp.edu.tw
(ShanC)
學校
:
臺北市立內湖高級中學
編號 : 138785
來源 : [118.167.222.118]
最後登入時間 ：
2024-05-23 14:23:16
題目要求輸入 n 然後找出 n 生成的數字是否為 3 的倍數
首先可以發現他生成的規律就是把 1~n 合起來，例如: n=6 生成 123456
其次題目說把每一位加起來然後 mod 3 可以判斷是否為 3 的倍數
根據一個性質: (a + b) mod p = ((a mod p) + (b mod p)) mod p
我們可以把生成的數字每一位都先 mod 3
接下來做前綴和 然後再對前綴和的每一項 mod 3
得以下表格:
| 第 i 位 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| mod 3 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 |
| prefix | 1 | 3 | 3 | 4 | 6 | 6 | 7 | 9 | 9 |
| prefix mod 3 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
經由表格可得到 prefix mod 3 的一個規律
在生成的數字中，第 1 + 3k 項必不為 3 的倍數
這結論可以用數學歸納法證明之
因此可得到以下 Python 參考程式碼:
n = int(input())
print('NO' if n % 3 == 1 else 'YES')
ZeroJudge Forum