作者JonathanWang (小尹)
看板ACMCLUB
標題Acm 10413
時間Sun Mar 23 16:32:42 2003
讓 m 從 max{C1, C2, .., Cn} 開始 試到 1000000
第一個試到的可行的 m 作為答案
測試的方式是對這 n 個 savages 兩兩計算
試試它們碰撞的時間是不是在 min{Li, Lj} 之後
而計算的方法是解下列方程式：
Ci + Pi * K ≡ Cj + Pj * K (mod m)
K 的最小正整數解
要解
(Pi - Pj) * K ≡ Cj - Ci (mod m)
令 Pi-Pj = A, Cj-Ci = B
可藉輾轉相除法求
A*K + m*L = B
中的 K 和 L
如果 gcd(A,m) 整除 B 就一定有解；否則一定無解，表示永不相撞
再試當地讓解得的 Ko 和 Lo 分別加上同樣倍數的
m B -A B
----------*---------- 和 ----------*----------
gcd(A,m) gcd(A,m) gcd(A,m) gcd(A,m)
把 K 變為最小的正整數解
時間約是
O(t*1000000*n*n*[100以內的兩整數輾轉所需運算次數])
--
※ 發信站: 批踢踢實業坊(ptt.csie.ntu.edu.tw)
◆ From: 140.112.244.210
※ 編輯: JonathanWang 來自: 140.112.244.210 (03/23 16:34)