本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-31 13:32:13

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;
}