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

设

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:

CPP

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

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

P2429 制杖题题解

文章操作

Code:

相关推荐

评论

P2429 制杖题题解