AtcoderBeginnerContest174 C問題の考察
ABC174Cの考察
こんにちは。numaです．
今回は前回のABC174がどうして解けなかったのか。どういう風に考えれば解けるのか。分析して自分の脳内を整理したいと思います．
筆者自身、まだまだ茶色の端くれで理解が甘いところがあると思うのでご指摘や別解等があると嬉しいです．
ABC174での出題問題
A: Air Conditioner
B: Distance
C: Respect
D: Alter Alter
E: Logs
F: Range Set Query
今回はCのRespectに着目します．
C: Respect
問題文
高橋君は K の倍数と 7 が好きです。
7,77,777,… という数列の中に初めて K の倍数が登場するのは何項目ですか？存在しない場合は代わりに -1 を出力してください。
制約
1≤K≤
K は整数である。
僕はこの問題を解いてて１週間は７が嫌いになりました．
むずかしくないか？？
とりあえず、num=7; num*=10; num+=7; するんだろうけど、、
明らかにオーバーフローするからどう対処するの、、、
longlongでやるにも18桁後にはオーバーフローを起こすしなぁ、、、
私はこのとき、modに着目しあまり理解をしていないフェルマーの小定理やmod逆元などについて調べてました．いけそうだけどいけない(心の声...)
では、解説に移りましょう．
と、その前にmodについてまとめます．
modとは
modとは余りを求める演算子のことでプログラミング言語ではしばしば「%」という演算子で求められます．Atcoderなどの競技プログラミングをしたことのある人は使ったことのない人はいないと思います．
例えば 20 (mod 3)を考えてみましょう．20を3で割った余りなので2となり
20 % 3 = 2
と計算してくれます．
これは 20 ≡ 2 (mod 3) と書きます．
解説
まず、アプローチとして
7, 77, 777, 7777, ...
の中でKの倍数となるのは何番目？という問題なので順番にmodを取ることで余りが０となるときに初めてKの倍数になることがわかります．
すなわち、modの世界で倍数判定を行えばうまくいくことがわかるでしょう．
例えば、入力例１を考えます．
input: 101, output: 4
なので、7777は101の倍数であることがわかるので、４番目の４が答えとなります．
これをmod 101 の世界で考えます．
ans = 1 のとき n = 7 ≡ 7 (mod 101)
↓ n = n*10 + 7
ans = 2 のとき n = 77 ≡ 77 (mod 101)
↓ n = n*10 + 7
ans = 3 のとき n = 777 ≡ 70 (mod 101)
↓ n = n*10 + 7
ans = 4 のとき n=7777 ≡ 707 ≡ 0 (mod 101)
↓ n = n*10 + 7
…
というように7, 77, 70, 0, 7, 77, 70, 0, ...というようなグラフ構造になることがわかります．よって、最初に余りが0になる、すなわち101の倍数となるのは4番目の7777が答えとなります．また、サンプルにもあるように入力が2の時は奇数である77...の倍数にはなり得ないことに注意してください．
これで解けました．プログラムは以下のようになります．
#include<bits/stdc++.h> using namespace std; #define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0); int main(){ fast_io ll k; cin>>k; if(k == 2){ cout << -1 << endl; return 0; } ll num=0; for(int i=1;i<2e6;i++){ num *= 10; num += 7; num %= k; if(num==0){ cout << i << endl; return 0; } } cout << -1 << endl; return 0; }
