题解：P12226 「WyOJ Round 1」启 · 破茧初阳

Tomwsc · 2025-04-18 18:33:52 · 题解

P12226 「WyOJ Round 1」启 · 破茧初阳 题解

思路

发现数据范围很大，所以我们考虑快速计算答案。如何快速计算答案呢？推式子！

很明显，这道题目只需要我们简单的推个式子即可。设在 n 以内能被 a 整除的数的个数为 x，能被 \operatorname{lcm}(a,b) 整除的数的个数为 y，能被 c 整除的数的个数为 z，能被 \operatorname{lcm}(a,c) 整除的数的个数为 p，能被 \operatorname{lcm}(a,b,c) 整除的数的个数为 q，答案为 ans，则有：

为什么，画个韦恩图然后容斥一下就清楚了……

如图，阴影部分即为所求。所以令人想到用 a 的圆圈加上 c 的圆圈。但因为橙色部分会被多次计算，所以剪掉 a 与 b 以及 a 与 c 重合的部分，即 \operatorname{lcm}(a,b) 和 \operatorname{lcm}(a,c)。此时，不难发现，绿色部分被多减掉了一次，所以还要再加回来，于是便有了加上绿色的部分，即 \operatorname{lcm}(a,b,c)。

接下来的问题就变成怎样计算最小公倍数了，有这么一个式子：

所以只要知道两数的最大公因数即可，辗转相除法可以计算两数的最大公因数，并且时间复杂度是 O(\log \min(a,b))。

代码

注意，数据很大，要开 __int128。

#include<bits/stdc++.h>
#define int __int128
#define inf (1ll << 62)
#define regint register int
#define pb push_back
#define mp make_pair
#define PII pair<int , int>
using namespace std;
int t , n , a , b , c;

int gcd(int a , int b) {
    if(!b)
        return a;
    return gcd(b , a % b);
}

inline int lcm(int a , int b) {
    return a / gcd(a , b) * b;
}

inline int read() {
    char c = getchar();
    int x = 0 , s = 1;
    while(c < '0' || c > '9') {
        if(c == '-')
            s = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * s;
}

void write(int x) {
    if(x >= 10)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

signed main() {
    t = read();
    while(t --) {
        n = read();
        a = read();
        b = read();
        c = read();
        write(n / a - n / lcm(a , b) + n / c - n / lcm(a , c) + n / lcm(lcm(a , b) , c));
        printf("\n");
    }
    return 0;
}