悲しみも、怒りも。全部因数分解してあげる。

私が寝ている間に、ヴェリタスの部員たちが仕事を片づけてくれたみたい。残るのは、ノアから渡された備品管理計画だけね。これをさっと計算して、大運動会の準備を終わらせましょう。

各競技で使う体育用の備品セットには、$1$番から$N$番までの番号をつけてあるわ。備品の組み合わせを使って、1つの競技$G$を開催できるの。

競技$G$は、次の条件を満たさなければならないわ。

• 競技$G$を開催するには、異なる番号の備品を2つ以上使う必要がある。
• 競技$G$で使う異なる備品をどの2つ選んでも、その番号の最大公約数は$K$でなければならない。

次は、複数の競技$G$からなる運動会計画$P$を作らなくちゃ。この計画$P$にも満たすべき条件があって頭が痛いけれど、メモにまとめてみましょうか。

• 運動会計画$P$では、同じ備品の組み合わせを使う競技を2つ以上開催することはできない。
• 運動会計画$P$に含まれる任意の競技$G$について、$G$より多くの備品を使う有効な競技が1つ以上存在する場合、そのような競技の一覧を$G'_1$、、、とする。競技で使う備品をすべて使う競技が、運動会計画に少なくとも1つ含まれていなければならない。

競技$G$をできるだけ多く含む運動会計画$P$を考えましょう。そのような計画$P$には競技$G$がいくつ含まれるか、ですって……。ノアに頼まれた仕事ではあるけど……これ、どう聞いても晄輪大祭の備品管理計画じゃなくて、ただのアルゴリズム問題じゃない？ ちょっと！ ノア！ どこへ行ったの！？

$G_4$より多くの備品を使う競技は存在しないため、$G_4$は運動会計画$P$に含めることができる。

競技$G_1, G_2, G_3$それぞれより多くの備品を使う競技$G_4$が存在する。

$G_1 \subset G_4, G_2 \subset G_4, G_3 \subset G_4$なので、$G_1, G_2, G_3$は運動会計画$P$に含めることができる。

したがって、運動会計画$P$に含まれる競技の数は$4$である。

実行時間制限

1000 ms

メモリ制限

1024 MB

チェッカー

CUSTOM