[APIO2019]奇怪装置。

题目

洛谷

题解

先来证明一个引理。
\(ac \equiv bc(modp),(c,p)=d\)则\(a \equiv b(mod \frac{p}{d})\)
\(\because ac ≡ bc(mod p)\)
\(\therefore p|ac-bc\)
\(\therefore p|c(a-b)\)
\(\because (c,p)=d\)
\(\therefore \frac{p}{d}|\frac{c}{d}(a-b)\)
\(\because c,p\)已经除去了\(gcd\)，
\(\therefore (\frac{p}{d},\frac{c}{d})=1\)
那么又\(\because\)整除
\(\therefore \frac{p}{d}|a-b\)
即\(a \equiv b(mod \frac{p}{d})\)

洛谷p5444 [APIO2019]奇怪装置