geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC186E Throne

ABC Baby-step Giant-step mod

Baby-step giant-stepによる解法とWeb公式解説の理解メモ

公式解説の理解
- をで割って良い理由
- の時に解なしになる理由
Baby-step giant-stepによる解法

公式解説の理解

$A,B,M$ を $d=gcd(A,B,M)$ で割って良い理由

$A' \leftarrow A/d,\ B' \leftarrow B/d,\ M' \leftarrow M/d$ とします。

$Ax \equiv B\ mod\ M$

を変形し、

$Ax-B \equiv 0\ mod\ M$

とします。

$Ax-B$ は $M$ の倍数となる必要があります。

$M$ の倍数であるとは、約数として $M$ を含むということです。

ここで、

$dA'x-dB'=d(A'x-B')$

となるので、

$A'x-B'$ が $M'$ の倍数なら、 $dM'$ を約数に含むこととなり、 $Ax-B$ は $M$ の倍数となります。

したがって、元の問題を

$A'x\equiv B' \ mod\ M'$

という問題に帰着させることができます。

$gcd(A',M') \neq 1$ の時に解なしになる理由

$A'x\equiv B'\ mod\ M'$

という問題は、

$A'x+M'y = B'$

を満たす整数 $x,y$ を求める問題とみなせます。この問題に解が存在するための必要十分条件は、

・ $B'$ が $gcd(A',M')$ で割り切れること

です。しかし、単にこの条件を見るだけでは、 $gcd(A',M')$ が必ずしも1である必要はありません。

では、なぜ解を持つ時に必ず $gcd(A',M')=1$ が成り立つことかを考えてみます。

$d'=gcd(A,M)$ とします。

(1) $d=d'$ のとき

すなわち $B$ が $d'$ を約数に持つ場合です。

この時、 $A',M'$ は共通の約数が無くなって、 $gcd(A',M')=1$ となります。

この時、当然 $B'$ を割り切ることができ、解を持ちます。

(2) $d\neq d'$ のとき

このとき、 $B$ は $d'$ に含まれる約数のうちの1つを持ちません。

それを $d''$ とおくと、 $gcd(A',M')=d'' \neq 1$ となります。

$B'$ も $d''$ を約数に持たないので、割り切れず、解なしとなります。

以上より、解を持たない時、 $gcd(A',M')\neq 1$ が示されました。

自分が疑問に感じたのはこれだけです。

次に、Baby-step giant-stepの考え方による解法を書いておきます。

Baby-step giant-stepによる解法

コンテスト当時にtwitterで言及されていたので、解いてみました。

この問題の解は非負整数 $n$ を用いて、

$nK+S\equiv 0\ mod\ N$

を求める問題に帰着されます。

ここで、 $m=\lceil \sqrt{M} \rceil$ とおきます。

$n$ は $m$ で割った商 $i$ と余り $j$ を用いて、 $n=im+j$ とおけます。

$0\leq i\lt m,\ 0\leq j\lt m$

なので、

$(im+j)K+S\equiv 0 \ mod\ N$
を満たすi,jの組を $O(m^2)(=O(N))$ で全探索できますが、これだと間に合いません。

そこで、式を変形して、

$jK+S\equiv -imK\ mod\ N$

とすると、 $j$ を含む左辺は右辺の $i$ の影響を受けず一定となります。

従って、予め $j = 0, 1, ..., m$ について、

$jK+S\ mod\ N$

を計算し、ハッシュマップなどに記録しておくことで、

$i=0,1,..,m$ について、

$-imk\ mod\ N$

と等しいものがあるかを $O(1)$ で判定できるようになり、全体で $O(m)(=O(\sqrt{N}))$ となります。

実装上、

・ $S$ を $gcd(N,K)$ で割った余りが0でない時は解なしとなり、これは予め判定しておく必要がある。

・ $jK+S\ mod\ N$ で同値なものが複数ある場合、 $j$ が最小のもののみ記録する。

という点に気をつけます。

計算量は公式解説より劣りますが、あまり深く考えなくて良いのは楽だと思いました。

提出コード