#42983: 所以輾轉相除法到底是啥
yp11251181@yphs.tp.edu.tw
(810-32張景翔)
學校
:
臺北市私立延平高級中學
編號 : 282413
來源 : [203.72.178.1]
最後登入時間 ：
2024-09-09 10:42:24
a024. 最大公因數(GCD)
| From: [203.72.178.1] |
發表日期
:
2024-10-14 09:51
如果有人不能理解輾轉相除法到底在幹嘛 我有一個理解方式
設被除數 x 除數 y
x%y = k
首先他會將大的數移到前面
然後 k=x%y=(x-ay)
也就是說k一定有x和y的最大公因數(分配律)
下一次就是x變成y的值 y變成k的值
可以看到如果一重複下去的話 最大公因數會一直存在在x,y中
最後y就只剩下最大公因數 然後就解出來了
ZeroJudge Forum