padic-aririri https://blog.hatena.ne.jp/padic-aririri/ Hello p-adic World https://padic-aririri.hatenablog.com/ AtCoder Beginner Contest 142のD問題の解説です。 問題の詳細は公式の問題ページをご確認ください。 問題文 正整数A,Bが与えられます。 AとBの正の公約数の中からいくつかを選びます。 ただし、選んだ整数の中のどの異なる2つの整数についても互いに素でなければなりません。 最大でいくつ選べるでしょうか。 制約 入力は全て整数である 1 ≤ A,B ≤ 10^{12} 入力 A B 出力 条件を満たすように選べる整数の個数の最大値を出力せよ。 解説 毎回、問題文を勘違いしやすいのですが、A,Bの公約数の作る集合の有限部分集合であって,任意の異なる2要素が互いに素となるよう… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpadic-aririri.hatenablog.com%2Fentry%2F2020%2F03%2F15%2F231110" title="ABC142-D - Hello p-adic World" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-03-15 23:11:10 rich https://padic-aririri.hatenablog.com/entry/2020/03/15/231110 1.0 100%