読者です 読者をやめる 読者になる 読者になる

Problem 134

ユークリッドの互除法を利用。

すると解けるらしいのでユークリッドの互除法 - Wikipediaユークリッドの互除法を再勉強.

使うのは拡張ユークリッドの互除法っぽい.
これは何に使えるかというと,

 拡張ユークリッドの互除法は,整数の合同における逆元を計算します。例として,合同式

12357 * x ≡ 102 mod 100102

を解いてみましょう。この合同式を解くとは,x を 12357 倍して,100102 で割ったときの余りが 102 となる整数 x をすべて求めることです。

で,結局 Problem 134 は,

10^d * x ≡ p1 mod p2 (d: p1 の桁数)

を満たす最小の x を求めればよいってことになる.


あとは普通に実装するだけ.