作者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)