結果

問題 No.3152 neither multiple of A nor B
コンテスト
ユーザー Cafe1942
提出日時 2025-05-10 08:41:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 603 bytes
コンパイル時間 658 ms
コンパイル使用メモリ 65,924 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-10 12:16:39
合計ジャッジ時間 1,703 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using namespace std;

long long gcd(long long a, long long  b) {
    long long  x, y, t;
    if (a > b) {
        x = a;
        y = b;
    }
    else {
        x = b;
        y = a;
    }
    while (y != 0) {
        t = x % y;
        x = y;
        y = t;
    }
    return x;
}

int main() {
	long long N, A, B;
	cin >> N >> A >> B;
    long long ans = N;//回答には包除原理を用いる。
    ans -= N / A;
    ans -= N / B;
    ans += N / (A * B / gcd(A, B));//最小公倍数は、(両数の積)/(それらの最大公約数)で求まる。
    cout << ans;
	return 0;
}
0