思路

把满足条件的数看成四个集合的并集：

• $A={k\in[1,n]\mid x\mid k}$（$x$ 的倍数）；
• $B={k\in[1,n]\mid y\mid k}$（$y$ 的倍数）；
• $C={k\in[1,n]\mid k\mid x}$（$x$ 的因子）；
• $D={k\in[1,n]\mid k\mid y}$（$y$ 的因子）。

直接对 $A\cup B\cup C\cup D$ 做四集合容斥代价较高，但注意：

• $A,B$ 的规模可用整除计数直接得到：

  

  于是 $|A\cup B|=|A|+|B|-|A\cap B|$。

• $C,D$ 的元素个数很少，因为一个数的因子个数在$10^9$ 范围内最多也就千级量级。我们可以在 $O(\sqrt{x})$ 与 $O(\sqrt{y})$ 的时间内枚举出 $x$ 与 $y$ 的全部因子，再筛掉 $>n$ 的因子即可。

做法如下： $1.$ 先计算

这是 $|A\cup B|$。

$2.$ 把 $x$ 与 $y$ 的所有不超过 $n$ 的因子放入一个集合（用哈希去重），得到集合 $S$。

$3.$ 对于 $S$ 中的每个 $d$，如果 $d$ 不属于 $A\cup B$（等价于 $d\bmod x\neq 0$ 且 $d\bmod y\neq 0$），则说明它只因“是因子”而特别，没有在 $M$ 中被计入，应补加 $1$。

$4.$ 答案为 $M+|{d\in S\mid d\bmod x\neq 0,d\bmod y\neq 0}|$。

这样避免了对四集合进行完整容斥，既简洁又高效。

C++

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

// 计算不超过 n 的 v 的所有因子
static vector<int64> divisors_leq(int64 v, int64 n) {
    vector<int64> res;
    for (int64 i = 1; i * i <= v; ++i) {
        if (v % i == 0) {
            if (i <= n) res.push_back(i);
            int64 j = v / i;
            if (j != i && j <= n) res.push_back(j);
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, x, y;
    if (!(cin >> n >> x >> y)) return 0;

    // 先处理 |A ∪ B|
    long long g = std::gcd(x, y);
    __int128 lcm128 = (__int128)(x / g) * y; // lcm 可能达到 1e18，用 __int128 保守计算
    long long both = 0;
    if (lcm128 <= (__int128)n) {
        both = (long long)((__int128)n / lcm128);
    } // 否则 both 保持为 0
    long long M = n / x + n / y - both;

    // 枚举 x 与 y 的因子（不超过 n），去重
    unordered_set<long long> S;
    auto dx = divisors_leq(x, n);
    auto dy = divisors_leq(y, n);
    for (auto d : dx) S.insert(d);
    for (auto d : dy) S.insert(d);

    // 统计需要额外补计的因子（不属于 A ∪ B）
    long long extra = 0;
    for (auto d : S) {
        if (d % x != 0 && d % y != 0) ++extra;
    }

    cout << (M + extra) << "\n";
    return 0;
}

Python

import sys
import math

def divisors_leq(v, n):
    # 返回 v 的所有不超过 n 的因子
    res = []
    i = 1
    while i * i <= v:
        if v % i == 0:
            if i <= n:
                res.append(i)
            j = v // i
            if j != i and j <= n:
                res.append(j)
        i += 1
    return res

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n, x, y = map(int, data)

    # |A ∪ B|
    g = math.gcd(x, y)
    lcm_xy = (x // g) * y  # Python 整数无溢出
    M = n // x + n // y - (n // lcm_xy)

    # 不超过 n 的因子集合（去重）
    S = set(divisors_leq(x, n)) | set(divisors_leq(y, n))

    # 统计额外补计的因子
    extra = sum(1 for d in S if d % x != 0 and d % y != 0)

    print(M + extra)

if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.util.*;

/*
  说明：
  - 使用 long 保证在 1e9 范围内的 lcm 乘积 (<=1e18) 不溢出。
  - 因子枚举为 O(sqrt(v))，对 x 与 y 各做一次，整体足够快。
*/
public class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    static ArrayList<Long> divisorsLeq(long v, long n) {
        ArrayList<Long> res = new ArrayList<>();
        for (long i = 1; i * i <= v; ++i) {
            if (v % i == 0) {
                if (i <= n) res.add(i);
                long j = v / i;
                if (j != i && j <= n) res.add(j);
            }
        }
        return res;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sp = br.readLine().trim().split("\\s+");
        long n = Long.parseLong(sp[0]);
        long x = Long.parseLong(sp[1]);
        long y = Long.parseLong(sp[2]);

        // 计算 |A ∪ B|
        long g = gcd(x, y);
        long lcm = (x / g) * y; // 在约束内不溢出
        long M = n / x + n / y - n / lcm;

        // 因子集合（不超过 n），去重
        HashSet<Long> S = new HashSet<>();
        for (long d : divisorsLeq(x, n)) S.add(d);
        for (long d : divisorsLeq(y, n)) S.add(d);

        // 统计需要额外补计的因子
        long extra = 0;
        for (long d : S) {
            if (d % x != 0 && d % y != 0) ++extra;
        }

        System.out.println(M + extra);
    }
}

题目内容

给你两个正整数 $x,y$ ，定义一个整数如果是特别的数，那么它一定满足以下条件至少其一：

• 它是 $x$ 的整数倍。

• 它是 $y$ 的整数倍。

• 它是 $x$ 的因子。

• 它是 $y$ 的因子。

给你一个整数 $n$ 请你求出 $1$ ~ $n$ 中有多少个整数是特别的数。

输入描述

输入一行三个整数 $n,x,y(1 ≦n,x,y ≦10^9)$ 如题意描述。

输出描述

输出一个整数表示 $1$ ~ $n$ 中特别的数的个数。

样例1

输入

10 3 5

输出

6