エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
ABC177 - EをRubyで解く - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
ABC177 - EをRubyで解く - Qiita
はじめに AtCoder Beginner Contest 177のE問題について細かく解説を書く機会があり、思いのほか出来が... はじめに AtCoder Beginner Contest 177のE問題について細かく解説を書く機会があり、思いのほか出来が良かったので記事としてまとめようと思う。 考察 問題より、焦点を以下の順番で三つに分割できる。 『全ての1 ≦ i < j ≦ N について、GCD(A_i, A_j) = 1』が成り立つ 『GCD(A_1 …… A_N) = 1』が成り立つ いずれも成り立たない 次より、これら三つをより細かく見ていく。 1.『全ての1 ≦ i < j ≦ N について、GCD(A_i, A_j) = 1』が成り立つ 全ての場合を愚直に求める。 N.times do |i| N.times do |j| if A[i].gcd(A[j]) != 1 then is_pairwise_coprime = false end end end 制約より、$2≤N≤10^6$ なので最大が