1

PILAME杯2024 予選問12 解説

406
0
$$$$

PILAME杯2024 予選問12の解説がインターネットのどこにも見当たらないので作問者が自分で解説します。

問題

$2024$以下の正整数が一つずつ書かれている黒板がある.積が平方数になるような$2$つの整数を消すという操作を何回も行えるとき,最終的に黒板に残った整数の個数の最小値を求めよ.

ネタバレ防止用余白

aaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
aabbbbbbbbbbbbbbaaaaaaaaabbbbbbbbbbbbbbb
abbbbbbbbbbbbaaaaaaaaaaaaaaabbbbbbbbbbbb
bbbbbbbbbbbaaaaaaaaaaaaaaaaaaabbbbbbabbb
bbbbbbbbbaaaaaaaaaaaaaaaaaaaaaabbbaaaaab
bbbbbbbbaaaaaaaaaaaaaaaaaaababaabbbaaabb
bbbbbbbaaaaaaaaaaaaaaaaaaababababbbaaabb
bbbbbbaaaaaaaaaaaaaaaaaaaabbbbbabbabbbab
bbbbbaaaaaaaaaaaaaaaaaabaaabbbaabbbbbbbb
bbbbaaaaaaaaaaaaaaaaaaabbaaaaaaabbbbbbbb
bbbbaaaaaaaaaaaaaaaaaaabbbaaaaaaabbbbbbb
bbbbaaaaaaaabaaaabaaaaabbbbaaaaaabbbbbbb
bbbbaaaaaaaabbaaabbaaabbbbbaaaaaabbbbbbb
bbbbaaaaaaaabbaaabbbaabbbbbaaaaaabbbbbbb
bbbbaaaaaaaabaaaabbbbabaaabaaaaaaabbbbbb
bbbbaaaaaaaaabbabbbbbbbabbabaaaaaabbbbbb
bbbbaaaaaabbabaabbbbbbbaababaaaaaabbbbbb
bbbbaaaaaabbabaabbbbbbbaababaaaaaaabbbbb
bbbbaaaaaabbabaabbbbbbbaabababbbaaabbbbb
bbbbaaaaaaabbbbbbbbbbbbbbbbbaaaaaaaabbbb
bbbbabaaaaabbbbbbbbbbbbbbbbbabbbaaaabbbb
bbbbabaaaaaabbbbbbbbbbbbbbbaabbbaaaabbbb
bbbbabaaaaaabbbbbbbbbbbbbbbaabbbaaaabbbb
bbbbabaaaaaabbbbbbaaaabbbbaaabbbaaaabbbb
bbbbbabaaaaaabbbbbaaaabbbbaaaaaaaaaabbbb
bbbbbbbaaaaaaaabbbbaabbbbaaaabbbaaaaabbb
bbbbbbbaaaaaaaaaabbbbbbaaaaaaaaaaaaaaabb
bbbbbbbaaaaaaaaaaaabbbaaaaaabaaaaaaaaaab
bbbbbbbaaaaaaaaaaabaaabaaaaabaaabaaaaaaa
bbbbbbaaaaaaaaaaaabbbbbaaaaabaaabaaaaaaa
bbbbbaaaaaaaaaaaaabbbbbaaaaaaaabbaaaaaaa
bbbbaaabaabbaaaaaaabbbaaaaaaaaabbaaabaaa
bbaaaabaaaaaaaaabbbaaabbbaaaaaaaaaaabbaa
aaaabbaaabaabbbbbbbbabbbbbbbaaaaaaaabbbb
bbbbbaaabaabbbbbbbbaabbbbbbbaaabbbaabbbb
bbbbaaabaabbbbbbbbaabbbbbbbaaabbbbbabbbb
bbaaabbaabbbbbbbbaabbbbbbbbaaabbbbbbabbb
aaaaabbabbbbbbbbaabbbbbbbbaaaabbbbbababb
bbabbaaabbbbbbbbabbbbbbbbbaaabbaababbbab
babbbbabbbbbbbbbabbbbbbbbaaabbaababbbbba

解説

正整数 $n$ を正整数 $a$ と平方因子を持たない正整数 $b$$n=a^2b$ と表すとき,2つの整数の組を消すことができる条件は $b$ が等しい事である.
この時、各 $b$ について消せる組の個数は,正整数 $x$ と平方因子を持たない正整数 $b$$n=(2x)^2b\leq 2024$ と書ける $n$ の個数と等しい.$n=(2x)^2b$ と書けることは $n$$4$ の倍数である事と同値なので、消せる組は $506$ 組になる.よって、$2024-506\times2=1012$ が答えになる。

投稿日:91

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

simasima
simasima
179
26150
OMC橙(2499/5位)OMC030,034,036,038優勝/OMC015,OMC032単独writer/AtCoder橙

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中