自动搬运

查看原文

来自洛谷，原作者为

	rfsfreffr Nothing is impossible

搬运于2025-08-24 21:37:36，当前版本为作者最后更新于2021-04-14 20:15:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

在机房颓废突然被拉过写制杖题

设$P_i$为$1,2,3...m$中能被$p_i整除的数的集合$,$Sum_i$为这个集合内所有数的和

初步思路为Ans=$\Sigma_{k=1}^{n}Sum_k$,但这样会有问题，比如样例中的p=3和5,若是使用这种方法，15的倍数会被计算2次。而且这只是两个质数，当$n$变大时，看起来似乎很难处理。

这时候我想到了容斥定理(具体计算公式我就不打了qwq),观察公式发现其中奇数个集合的并集的符号都是$+$，偶数个集合的并集的符号都是$-$。于是我想到了深搜，即计算所有小于$m$的能被$p$组成的数（由题意可知其不含平方因子）

我已开始觉得这种做法可能会TLE。

然后我发现$2*3*5*7*11*13*17*19*23*29=6469693230$（即前几个质数的乘积）$>=1e9$

也就是说被$p$组成的数含p的因子个数其实最多只有9个，显然时间复杂度没有想象中的那么高。于是马上开搞。

Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
int p[100001];
int a[201];//用a记录这个质数是否取过了

int ans;
void dfs(int x,int sum) {//x为取到第几个质数了，显然取了一个编号为n的质数不能再取一个编号为m(m<n)的质数，否则有可能会由部分乘积被重复计算多次
	int p0=1;
	for(int i=1; i<=n; i++) {//算出当前取出的这个数
		if(a[i]==1) p0*=p[i];
	}
	if(p0>m) return ;
	int t=m/p0;
//	cout<<p0<<endl;
	if(sum%2==1)ans=ans+((1+t)*t/2)%376544743*p0;//奇数个质数的乘积就相加，偶数个质数的乘积就相减
	if(sum%2==0) ans=ans-((1+t)*t/2%376544743)*p0;
	ans%=376544743;

	for(int i=x+1; i<=n; i++) {
		if(a[i]==0) {
			a[i]=1;
			dfs(i,sum+1);
			a[i]=0;
		}
	}
}
signed main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		cin>>p[i];
	}
	for(int i=1; i<=n; i++) {
		memset(a,0,sizeof(a));//每次记得清0
		a[i]=1;
		dfs(i,1);
	}
	cout<<ans<<endl;
	return 0;
}

有段时间没写题解了，有些表述方面可能有问题，望指出