AtCoder ABC 174 C - Repsept (300点)

https://gyazo.com/0e5dd2ba22a4f3a79ffdb9e8979ee270

考察履歴

コンテスト中に考えたこと（筋の悪い方針）

7...7は1...1*7の数字

問題名は Repseptなので、これをもじったもののよう

7...7という数列は、とても大きい値になるので、桁数だけをうまく取得したい、と考えた。

この「ある関数に入れると答えとなる桁数を得る」、みたいな考え方が非常によくない。

結果的にそのような関数の形をとるような可能性もあるかもしれないが

この考え方は全く逐次的でない、問題を解く姿勢として誤っている

この姿勢、思考になったら要注意。筋の悪い方針に向かっている可能性がある

解説pdfも私では理解できず、解説動画でようやく理解できました。

解説動画救い

解説動画からの考察/理解

1項目:7,2項目:77,3項目:777,4項目:7777,5項目:7777,...

Kの倍数となる7...7は何番目(何項目)？という問題

最初は「何項目（コウメ）」という言葉にちょっと詰まった。何項目（ナンコウモク）と読んだりもした。。

「何番目」という問い。

解答にたどり着くには、modの数学知識、感覚が必要。

7からなるものの、数字の性質について考える

おまけ

数式で、代数的に考えると、、、

例　

$ S=777

$ 10*S=7770

$ 9S=7000-7(=6993)

$ S=(10^i-7)/9

漸化式で考える

余りに対して、漸化式で次の項を求める

そして余りの数値の遷移をグラフに表現することができる！幾何の世界へ！

ファンクショナルグラフと言ったりするよう

（ここらへんの解説聞いているとき奮えた）

https://gyazo.com/3c90291e1963cceb2e2e1dfc21c7cb8e

以上の考察を用いることで解答となる実装ができるようになる！

解説動画が本当に丁寧で感謝しかない。

心に残った発言

「modの数学知識、感覚が必要」

「modKで考える」

「というわけでグラフの問題になりました」

「数列に綺麗な規則があると信じて考えないといけない」

「ソースコードは簡単だが、思考過程はmodの数学に慣れていないと難しい」

ACコード（写経）

code:rust

use std::io::*;

use std::str::FromStr;

use std::collections::HashSet;

fn read<T: FromStr>() -> T {

let stdin = stdin();

let stdin = stdin.lock();

let token: String = stdin

.bytes()

.map(|c| c.expect("failed to read char") as char)

.skip_while(|c| c.is_whitespace())

.take_while(|c| !c.is_whitespace())

.collect();

token.parse().ok().expect("failed to parse token")

}

fn main() {

let k:u64 = read();

let mut s = HashSet::new();

let mut x = 7%k; //let mut x = k;

let mut i = 1; //let mut i = 0;でも良い

//重複訪問が発生したらループを抜ける

while s.contains(&x) == false {

if x == 0 {

println!("{}",i);

return;

}

s.insert(x);

x = (x*10+7)%k;

i += 1;

}

println!("-1");

}

手元のSurface Goでやると入力例3が2秒では終了しなかったが、submit先では100msオーダで完了した。