「WyOJ Round 1」启 · 破茧初阳

· · 题解

Solution

算法标签： 容斥原理。

上图给出了所求答案的范围。被 a 整除且被 b 整除的数量为

\left\lfloor \frac{n}{\mathrm{lcm}(a,b)} \right\rfloor

那么，被 a 整除且不能被 b 整除的数量为

\left\lfloor \frac{n}{a} \right\rfloor - \left\lfloor \frac{n}{\mathrm{lcm}(a,b)} \right\rfloor

被 c 整除的数量为

\left\lfloor \frac{n}{c} \right\rfloor

此时，已经计算了红色和蓝色的区域：

不难发现，中间的小区域被算了 2 次，需要减去。中间的小区域为

\left \lfloor \frac{n}{\mathrm{lcm(a,c)}} \right \rfloor-\left \lfloor \frac{n}{\mathrm{lcm(a,b,c)}} \right \rfloor

综上，答案为

\left\lfloor \frac{n}{a} \right\rfloor - \left\lfloor \frac{n}{\mathrm{lcm}(a,b)} \right\rfloor+\left\lfloor \frac{n}{c} \right\rfloor-\left \lfloor \frac{n}{\mathrm{lcm(a,c)}} \right \rfloor+\left \lfloor \frac{n}{\mathrm{lcm(a,b,c)}} \right \rfloor

Code

// 验题人（KSCD_）代码
#include<iostream>
#define ll long long
#define i128 __int128
using namespace std;
const int N=1e5+10;
i128 gcd(i128 a,i128 b) {return b?gcd(b,a%b):a;}
i128 read() {ll x; cin>>x; return x;} 
i128 lcm(i128 a,i128 b) {return a*b/gcd(a,b);}
void sol()
{
    i128 n=read(),a=read(),b=read(),c=read();
    ll res=n/a-n/lcm(a,b)+n/c-(n/lcm(a,c)-n/lcm(lcm(a,b),c));
    cout<<res<<'\n';
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int TT; cin>>TT;
    while(TT--) sol();
    return 0;
}