前半は自明です。後半は次の問題に帰着されます
ばかでかい正の整数Mがあります。でかすぎて値はわかりません。正の整数nを渡すとMをnで割ったあまりを返すオラクルが定数回使えます。
ax=b mod M を満たす最小の非負整数xをmで割ったあまりを求めてください。gcd(a,M)=1とします。
たぶんやってることは公式解説と同じです。こっちの方が俺には自然
以下、大文字は計算不可能な値を、小文字は計算可能な値を表すこととします。
まずオラクルを呼んでr:=M%aを求めます。Q:=floor(M/a)としてr=M-aQとなります。
a,rに対して拡張gcdをしてsa-tr=1となる非負整数s,tを求めます。r=M-aQを代入して、a(s+tQ)=1 mod Mを得ます。
a^-1 mod Mが求まったのでこれにbを掛けて、x=b(s+tQ) mod Mです。求める答えはb(s+tQ)をMで割ったあまりをmで割ったあまりです。
0<=u< aによりbt=av+uと書くと、btQ+bs=uQ+(bs-rv) mod M です。
uQ+(bs-rv)が答えなら嬉しいですね。確かめます。
uQ<=(a-1)Q<((a-1)/a)Mなので、a(bs-rv)<=M なら uQ+(bs-rv)< Mです。u>0なら同様にuQ+(bs-rv)>=0です。
u=0かつbs-rv<0のケースは簡単なので適当に処理することにすれば、uQ+(bs-rv)が答えといって良いことになります。
ということであとはQ=floor(M/a)をmで割ったあまりが分かればOKです。これはARCでやりました。
https://atcoder.jp/contests/arc111/tasks/arc111_a
おわりです。
こういうのはQとrを使ってガチャガチャやると解けがち
