[Acwing] 890.能被整除的事 二进制枚举+容斥原理

前言

原来容斥原理还是有公式的

传送门 :

思路

一开始做的时候以为可以正难则反,但是实际做了发现还是正才行。

对于一个数,我们在筛法里面知道可以用它的倍数表示即

n / s [ i ] n/s[i] n/s[i]

对于几个数一起,因为是素数我们可以直接把他们相乘

然后就是套这个公式了:

CODE

void solve()
{
	cin>>n>>m;
	for(int i=0;i>p[i];
	
	for(int i = 1;i