AtCoder Beginner Contest 174, C : Repsept

問題文

　https://atcoder.jp/contests/abc174/tasks/abc174_c

問題概要

　$7, 77, 777, \dots$ という数列を考える．
　整数 $K$ が与えられる．上記の数列中で，$K$ の倍数が初めて出現するのは何項目か？　出現しない場合は $-1$ を出力せよ．

制約

• $1 \leq K \leq 10^6$

解法

　ある数 $a$ が $K$ の倍数であるということは，$a \bmod K = 0$ と言い換えられます．
　また，数列のある項から次の項を生成するには，元の項を $10$ 倍して $7$ を足せばよいです．よって，数列のある項の $\pmod K$ の値が $m $ だったとき，次の項の $\pmod K$ の値 $m'$ は，$$m' = ( 10m + 7 ) \bmod K$$ と計算できます．$\pmod K$ の値というのは高々 $K$ 種類の値しかとれないので，解があるならば $K$ 項以内に出現します．
　$K$ の値は扱える程度の大きさなので，これで問題を解くことができます．この解法は，$\pmod K$ の値をもっておいて高々 $K$ 解更新するので，$O( K )$ 時間で動作します．

コード

constexpr auto INF = LIM<>::max() / 2;

int main()
{
	IN( int, K );

	int c = 7 % K;
	VI dp( K, INF );
	dp[c] = 1;

	while ( c )
	{
		const int nc = ( c * 10 + 7 ) % K;
		if ( !chmin( dp[ nc ], dp[c] + 1 ) )
		{
			cout << -1 << endl;
			return 0;
		}
		c = nc;
	}

	cout << dp[0] << endl;

	return 0;
}