きろく

特筆すべき記録のまとめ

yukicoder:No.826 連絡網

問題

yukicoder.me

解法

P = 1 または N / 2 より大きい素数のとき答えは 1.なぜならば,前者は自明で,後者は 2 * P が N を超えてしまうため,1 ~ N の数の中で 2 と P をかけて合成数を作ることが出来ないから.

そうでないとき,家 i(i は N / 2 以下の素数)は家 P(P は N / 2 以下の素数,または,N 以下の合成数)と連結になることが出来る.なぜならば,家 i は家 2 * i (<= N) と連結であり,家 2 * i は家 2 と連結であるので,家 i は家 2 と連結になる.一方,家 P は家 i と同じ原理か,P 自体が合成数であるので(合成している数で一番小さい数は必ず N / 2 以下であるので)家 2 と連結である.なので,家 i と家 P は連結になる.また,家 j (j は N 以下の任意の合成数) も同様に家 P と連結になる.よって,答えは N - (N / 2 より大きい素数の数) となる.O(N√N).

解答

yukicoder.me

f:id:babcs2035:20190505145140p:plain