AtCoder Beginner Contest 186, E : Throne

問題文

　https://atcoder.jp/contests/abc186/tasks/abc186_e

問題概要

　正整数 $N, S, K$ が与えられる．$S + xK \equiv 0 \pmod N$ となる最小の $x$ を求めよ．
　$T$ ケース処理せよ．

制約

• $1 \leq T \leq 100$
• $2 \leq N \leq 10^9$
• $1 \leq S \leq N$
• $1 \leq K \leq 10^9$

解法

　Baby-Stap Giant-Step のような考え方で解いていきます．
　まず，$M = \lceil \sqrt N \rceil$ とします．元々求めたい答えは $S + xK \equiv 0 \pmod N$ となる整数 $x$ でしたが，$M $ と $y, z \leq M $ なる $y, z$ を使って $S + ( yM + z )K \equiv 0 \pmod N$ とも書けます（$x \geq N$ なる $x$ をかけると循環してしまうので，$yM + z < N$ です）．この条件を満たす $y, z$ について，$yM + z$ が最小のものを求めることができれば，その $yM + z$ が答えです．
　ここで，もし $y$ の値が固定されているとすれば，残っている問題は，$S' = ( S + yKM ) \bmod N$ として，$zK \equiv N - S' \pmod N$ となる $z$ が存在するかどうかを判定し，存在すればそれを求めることです．$z$ の値というのは先程の議論から $M $ 以下でしたから，その候補というのは $\Theta( \sqrt N )$ 個です．この程度ならば前計算しておくことができて，$z$ の候補 $i$ をすべて試し，
\begin{align*}
c_a = \begin{cases}
\min I & \text{($I$ は $iK \equiv a$ なる $i$ の集合で，$I \neq \emptyset$)} \\
\mathrm{undefined} & \text{(otherwise)}
\end{cases}
\end{align*}
のような配列（的なもの）を用意しておけば，この配列を参照するだけで求められます．あとは $y$ の値を全通り（$\Theta( \sqrt N )$ 個）試すことで，問題を解くことができます．
　$c$ の一要素あたりの更新・取得に $P( N )$ 時間がかると仮定すれば，前計算で $\Theta( \sqrt N )$ 回の更新が発生し，答えを求めるパートで $\Theta( \sqrt N )$ 回の読み出しが発生するので，全体の計算量は $\Theta( P( N ) \sqrt N )$ 時間となります．

コード

int solve()
{
	IN( int, N, S, K );
	K %= N;

	const int b = ceil( sqrt( N ) );

	unordered_map< int, int > coefficients;
	REP( i, b + 2 )
	{
		const int k = LL( i ) * K % N;
		if ( !EXISTS( coefficients, k ) )
		{
			coefficients[k] = i;
		}
	}

	REP( i, b + 1 )
	{
		const int s = ( S + LL( K ) * b * i ) % N;
		const int t = N - s;
		if ( EXISTS( coefficients, t ) )
		{
			return i * b + coefficients[t];
		}
	}

	return -1;
}

int main()
{
	IN( int, T );
	REP( T )
	{
		cout << solve() << '\n';
	}
	cout << flush;

	return 0;
}