第24回日本情報オリンピック　一次予選(第3回)

2024年11月18日
情報オリンピック日本委員会

解説

整数の入力，足し算，割り算，条件分岐，整数の出力，および決まった数ではない回数だけ繰り返しを行う処理ができれば解くことのできる問題である．

はじめに，カウンター変数 cnt を 0 で初期化する．

その後，for 文を用いて i = 1, 2, …, N とし，各 i について

• A で割り切れるが，B で割り切れない
• B で割り切れるが，A で割り切れない

のいずれかであるならば cnt に 1 を加算する．

最終的に得られた cnt が求める個数であるため，これを出力する (C++ による解答例)．

この問題で与えられる N の制約の範囲では上述の方針で十分高速に答えを求めることができるが，熱心な読者のために，より大きな N についても高速に動作する方針を以下に示しておく．

はじめに、先に挙げた解答例の計算量は O(N) である，すなわち，プログラムは N に比例した回数だけ計算処理を行うことになる．プログラムの実行にかかる時間は計算処理の回数におよそ比例するため，N が 10¹⁸ ほどに大きい値を取りうる場合，実行には膨大な時間がかかってしまう．

計算処理の回数が N に比例するのは for 文によるループがボトルネックとなっているため，このループを用いずに問題を解くことを考える．

具体的には，1 以上 N 以下の整数のうち，

• 「A で割り切れるが B で割り切れないもの」の個数は 「A で割り切れるもの」の個数から 「A と B の両方で割り切れるもの」の個数を引いたものに等しい
• 「B で割り切れるが A で割り切れないもの」の個数は 「B で割り切れるもの」の個数から 「A と B の両方で割り切れるもの」の個数を引いたものに等しい

ことを利用する．

1 以上 N 以下の整数のうち，

• 「A で割り切れるもの」の個数は N ÷ A の小数点以下切り捨てにより
• 「B で割り切れるもの」の個数は N ÷ B の小数点以下切り捨てにより
• 「A と B の両方で割り切れるもの」の個数は N ÷ lcm(A, B) の小数点以下切り捨てにより

求められる (ここで，lcm(A, B) は A，B の最小公倍数を表す) ．

ここに，lcm(A, B) = (A × B) ÷ gcd(A, B) (ここで gcd(A, B) は A，B の最大公約数を表す) であることに注意すると，多くの言語に実装されている gcd(A, B) 関数を用いることで，lcm(A, B) は非常に高速に求めることができる (具体的には log(max(A, B)) に比例した計算量．詳しくは「ユークリッドの互除法」と調べてみるとよい．)．

多くの言語に実装されている整数切り捨て除算を用いると，Python による解答例のような実装となる．