题解：P2429 制杖题

题意

求不大于

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代码

CPP

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

题解：P2429 制杖题

文章操作

题意

思路

AC代码

相关推荐

评论

题解：P2429 制杖题