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; } };