FPS24題B - 整数の組

なんで気づかなかったんだシリーズ

問題文

整数 が与えられます。次の条件を全て満たす非負整数の組 の個数を で割った余りを求めてください。

• 
• は または
• は または または
• は偶数
• は の倍数

制約

• 
• は整数

解法

とおきます。この時、 の制約より任意の について、 を満たす の組がちょうどひとつ対応します（ を で割った商と余りを考えると明らか）。

についても同様に、 の組が一対一対応します（ を で割った商と余り）。

よって結局 かつ を満たす を数えればよく、これは 通りです。