P2429 制杖题题解

· · 题解

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

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

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