Fractionの別解について
別解とか言ってますが、この解法の人も結構いて安心しました。
joisc2008.contest.atcoder.jp
この問題、想定解だとファレイ数列というのですが、僕はその解法ではなかったので雑に解説します。
注目するべき点
k<=200000
これで、0からkまでループさせればいいということがわかりますね。
ここからは発想です、そのまま解を載せます
1/nから1/2までsetにいれる
i/a<(i+1)/aは自明なので、i/aが消去されれば(i+1)/aをsetにいれる
これだけでなんとかなります。
あとは、i+1とaの最大公約数が1出ないといけない、とかありますが、そこら辺は実装して気づくと思います。
時間に非常に焦っていたので、残念ながら雑になりました。申し訳ないです。
