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

EDG_AKUYTRE · 2025-04-18 22:42:01 · 题解

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

不难发现是容斥，不妨设条件 A 为当前年份能被 a 整除且不能被 b 整除，条件 B 为能被 c 整除，则答案为：满足条件 A 的年份数 + 满足条件 B 的年份数 - 同时满足条件 A 和条件 B 的年份数。求 \operatorname{lcm} 可以通过 a×b÷\gcd(a,b) 得到，因为两个数的最小公倍数与两个数的最大公约数的成绩就是这两个数的乘积。

注意中间结果会爆 long long ，可以上 __int128 。

很简单，直接上代码。

#include<iostream>
#include<cstdio>
#include<map>
#define int __int128
using namespace std;
inline int read(){
    char ch=getchar();int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int gcd(int a,int b){
    if(!b)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a*b/gcd(a,b);
}
int solve(int n,int a,int b,int c){
    int cnt1=n/a-n/lcm(a,b);
    int cnt2=n/c;
    int cnt3=n/lcm(a,c)-n/lcm(lcm(a,b),c);
    return cnt1+cnt2-cnt3;
}
int T;

signed main(){
    T=read();
    while(T--){
        int n,a,b,c;
        n=read();a=read();b=read();c=read();
    //  cin>>n>>a>>b>>c;
        int ans=solve(n,a,b,c);
        write(ans);
        cout<<'\n';
    }
    return 0;
}