T162491 [Round 1]整除(同余方程&exgcd)
s o l v e : solve: solve:
{ x = 10 m + n ( 1 ) y = a m + b n ( 2 ) \begin{cases}x=10m+n\ \ (1)\\y=am+bn\ \ (2)\end{cases} {x=10m+n (1)y=am+bn (2)?，考慮得到 x , y x,y x,y的關系，
( 1 ) (1) (1)式同乘 b b b，消掉 b n bn bn，
→ y = b x + m ( a ? 10 b ) \rightarrow y=bx+m(a-10b) →y=bx+m(a?10b)
又因為 p ∣ y → p ∣ x p|y\rightarrow p|x p∣y→p∣x
可推出
a
≡
10
b
(
m
o
d
p
)
a\equiv 10b \pmod{p}
a≡10b(modp)
題目要求出最小的
a
>
0
a>0
a>0，
考慮轉化該式子： 10 b + p x = a 10b+px=a 10b+px=a關于 b , x b,x b,x的方程，
由裴蜀定理可知， g c d ( 10 , p ) ∣ a gcd(10,p)|a gcd(10,p)∣a，則 a a a的最小值是 g c d ( 10 , p ) gcd(10,p) gcd(10,p)，
求出 a a a，后等式兩邊同除 a a a，推出 t m p × b + p ′ × x = 1 tmp\times b+p'\times x=1 tmp×b+p′×x=1，
利用擴展歐幾里得可得出 b , x b,x b,x的值，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/260654.html
標籤：其他