洛谷P2429 制杖题 题解

题目链接：P2429 制杖题

题意：

求不大于 \(m\) 的、质因数集与给定质数集有交集的自然数之和。

输入格式：

第一行，两个整数 \(n, m\)。

第二行，\(n\) 个整数，表示质数集内的元素 \(p_i\)。

输出格式：

一个整数，表示答案，对 \(376544743\) 取模。

数据范围：

测试点编号	规模
\(1 \sim 3\)	\(n m \le {10}^7\)
\(4 \sim 5\)	\(n \le 2\)，\(m \le {10}^9\)
\(6 \sim 7\)	\(n \le 20\)，\(m \le {10}^8\)
\(8 \sim 10\)	\(n \le 20\)，\(m \le {10}^9\)

对于 \(100 \%\) 的数据，\(1 \le n \le 30\)，\(1 \le m \le {10}^9\)。

数据范围可能有点令人迷惑，我猜它是指测试点 \(1\sim 3\) 满足 \(n \le 30\) 。

记 \(S_i=\sum_{p_i \mid x \,\land \, x \le m} x\) ，如果我们直接计算 \(\sum S_i\) ，会出现重复计算的情况。

不妨记 \(T_i = \{x\mid (p_i \mid x) \,\land\,x \le m\}\) ，我们要求的实际上是 \(\bigcup_{i=1}^{n} T_i\) 的所有元素的和。

那么这就是一个容斥的事了 \[ S\left(\bigcup_{i=1}^{n} T_i\right) = \sum_{1\le i\le n} S(T_i) - \sum_{1 \le i < j \le n}S\left(T_i \cap T_j\right) + \cdots + (-1)^{n-1}S\left(\bigcap_{i=1}^{n} T_i\right) \] 可以发现，如果一个数 \(x\) 有奇数个 \(p_i\)​ ，那么它对答案的贡献为正，反之为负。

因为 \(m\) 的范围使得 \(n\) 个质数很难同时出现，所以考虑暴力dfs所有的组合方式和顺序来模拟容斥

当前质数 \(p_0\) 的贡献即为 \(p_0 \times \frac{r(r+1)}{2}\) ，其中 \(r= \left\lfloor\frac{m}{p_0}\right\rfloor\) 。

时间复杂度 \(\mathcal{O}(\mathrm{ok})\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int P = 376544743;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= P ? x -= P : 0; }
#define N ((int)(105))

int n,m,res,p[N];char c[N];
void dfs(int u, int cnt)
{
    int p0 = 1;
    for(int i = 1; i <= n; i++) if(c[i]) p0 *= p[i];
    if(p0 > m) return;
    int r = m / p0, f = (r + 1) * r / 2 % P;
    (cnt & 1) ? add(res, p0 * f % P) : add(res, P - p0 * f % P);
    for(int i = u; i <= n; i++) if(!c[i]) {
        c[i] = 1; dfs(i, cnt + 1); c[i] = 0;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> p[i];
    sort(p + 1, p + 1 + n); n = unique(p + 1, p + 1 + n) - p - 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) c[j] = false;
        c[i] = true; dfs(i, 1);
    }
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/yjj2015yjj/solution-p2429