アルゴリズムと数学 実演問題集 007についての質問

Question

実現したいこと

AtCoder上で以下のプログラムを提出すると不正解(WA)となります。何が間違っているのかを知りたいです。

問題文

N以下の正の整数の中で、Xの倍数またはYの倍数であるものの個数はいくつありますか？

• 制約
  1≤N≤10^6
  1≤X<Y≤10^6
  入力は全て整数

• 入力
  入力は以下の形式で標準入力から与えられます。

N X Y

• 出力
  答えを出力してください。

該当のソースコード

#include <iostream>
using namespace std;

int N, X, Y;
int Ans;

int main(){
    cin >> N >> X >> Y;

    Ans += (N / X);
    Ans += (N / Y);
    Ans -= (N / (X * Y));
    
    cout << Ans << endl;
}

リンク

AtCoderでの当該問題

Comments

[melian]

例えば、Y が X の倍数になっている場合を考えます。

N = 10, X = 2, Y = 4

質問文にあるコードを実行すると結果は 6 になります。ですが、実際には 2, 4, 6, 8, 10 が該当しますので正解は 5 になります。
もっとも、この条件を考慮したコードでも WA が出ますが。

[N.hajik]

回答ありがとうございます。確かに、X,Yに公約数がある場合に上手くいきませんね。

Answer 1

以下の入力例に対し、正しい出力は4になるはずですが(4, 6, 8, 12)、ご提示のコードだと5になります。

12 4 6

Comments

[N.hajik]

回答ありがとうございます。確かに、X,Yに公約数がある場合に上手くいきませんね。