2元1次不定方程式とAtCoder ABC186 E-Throne（後編）

１．はじめに

前編で2元1次不定方程式について、中編で拡張ユークリッドの互除法について書きました。後編では、ABC186 E-Throne について書いていきたいと思います。

２．問題概要

1<S<N を満たす整数 S , N がある。また 1以上の整数K があり、0以上の整数x があり、S＋Kx が N の倍数であるような、最小の整数x を求めよ。ただし、そのような x がない場合は、-1 を答えよ。T個のクエリについて答えよ。(1<=T<=100)

３．考察

S+Kx=Np (pは整数) という等式が成り立つので、Kx-Np=-S という形の2元1次不定方程式を満たすような、最小の整数x を求めるということになります。-p=y とおくと、Kx+Ny=-S となり、KとN が互いに素であるか、KとNとSの最大公約数をg とすると、KとNをgで割った数の組が、互いに素であるときにx が存在します。互いに素でないのであれば、前編で見たように解を持たないので、-1 を出力します。