题解：P2429 制杖题

HRS_ren_zheng_hang · 2025-08-03 16:58:31 · 题解

题意

求不大于 m 的自然数中，能被给定 n 个质数中至少一个质数整除的数之和。（n\le 30，m\le 10^9）

思路

我们发现直接计算和从反面计算都不好做，所以考虑容斥。

如果直接枚举子集，发现 n\le30，不能通过。

但不难发现，很多子集的乘积都远大于 m，不会对答案产生贡献。事实上，对答案有贡献的子集大小最多为 9，因为 2*3*5*7*11*13*17*19*23*29>10^9。

于是，我们可以使用dfs枚举集合，当乘积超过 m 时，直接剪枝掉即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=376544743;
long long ans;
int n,m,p[35];

int f=-1;
void dfs(int i,long long x)
{
    if(x>m)return;
    if(i==n+1)
    {
        if(x!=1)ans=(ans+(m/x*(m/x*x+x)/2)*f)%mod;
        return;
    }
    f*=-1;
    dfs(i+1,x*p[i]);
    f*=-1;
    dfs(i+1,x);
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",p+i);
    dfs(1,1);
    printf("%lld",ans);
    return 0;
}