SRM 390 250pt: ConcatenateNumber

問題概要

整数N(<10^9)とK(<10^4)が与えられる。Nを何回連結させたらKの倍数になるか求める問題。無理な時は-1を返す。

考えたこと

  • 問題文短くていいなあ。
  • MOD K。やるだけっぽい。一応オーバーフローに注意。
  • 何か合わないと思ったら更新の仕方がcur = (cur * d + cur) % Kになってた。+ curではなくて + Nだ。
  • 訂正。無事通った。

practiceで通ったコード

計算量O(log N + K)。

typedef long long int64;

struct ConcatenateNumber {

	int getSmallest(int number, int k) {

		//numberは何桁?
		int64 d = 1;
		for(d=1; number/d > 0; d*=10);

		int64 cur = number % k;
		for(int i=1; i<=k; i++){
			if(cur % k == 0){
				return i;
			}
			cur = (cur * d + number) % k;
		}
		return -1;
	}

};