嘘~ 正在从服务器偷取页面 . . .

洛谷P2429 制杖题题解

发布日期: 2024-02-16

更新日期: 2024-02-18

文章字数: 663

洛谷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 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$

数据范围可能有点令人迷惑，我猜它是指测试点 $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;
}