anyiak
立身须正,为人当明
安逸的网络日志

P1082 [NOIP2012 提高组] 同余方程

题中$$ax \equiv 1\pmod{b}$$这个式子,根据同余的定义,

$$ax \mod b=1 \mod b$$

$1$模任何数都余$1$,所以$$ax \mod b=1$$

根据模运算的性质得

$$ax-by=1$$

于是这个方程就转化成了一个漂亮的不定方程,可以用exgcd求解。

发表评论

textsms
account_circle
email

安逸的网络日志

P1082 [NOIP2012 提高组] 同余方程
题中$$ax \equiv 1\pmod{b}$$这个式子,根据同余的定义, $$ax \mod b=1 \mod b$$ $1$模任何数都余$1$,所以$$ax \mod b=1$$ 根据模运算的性质得 $$ax-by=1$$ 于是这个方…
扫描二维码继续阅读
2021-01-19