自动搬运

查看原文

来自洛谷，原作者为

	阿丑 ArrTue

搬运于2025-08-24 22:00:14，当前版本为作者最后更新于2022-11-03 14:44:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

update：修改了一些 LaTeX 问题（\not\mid->\nmid），增加了 k 的数据范围。

题目传送门

前置知识：

扩展欧几里得算法，容斥 / 子集反演。

题意：

• 给定 $n$，表示有一个长为 $n$ 的未知数组 $x$。
• 给定 $m$ 个数 $k_i$，表示 $\forall t<\frac x{k_i},t\in\mathbb N$，已知 $\sum_{i=tk_i+1}^{\min(n,(t+1)k_i)}x_i$。
• 问有多少 $i$ 满足 $x_i$ 被唯一确定。
• $2\le k_i<n\le10^9$，$m\le10$。

分析：

记 $s$ 表示 $x$ 的前缀和，即 $s_i=\sum_{j=1}^ix_j$。

则条件即为已知 $s_k-s_0,\,s_{2k}-s_k,\,\dots,\,s_n-s_{tk}$。又已知 $s_0=0$，故条件转化为已知 $s_k,s_{2k},\dots,s_n$，即已知若干个前缀和。所以，$x_i$ 被唯一确定，当且仅当 $s_i$ 与 $s_{i-1}$ 均已知。

考虑哪些 $i$ 满足 $s_i$ 已知。由上述分析知 $s_i$ 已知当且仅当 $\exists k_j,k_j\mid i$ 或 $i=n$。为了方便，我们令 $k_{m+1}=n$。这样，$s_i$ 被确定当且仅当 $\exists k_j,k_j\mid i$。

考虑哪些 $i$ 满足 $x_i$ 被确定，即 $s_{i-1}$ 与 $s_i$ 均已知。$x_i$ 被确定当且仅当 $\exists k_{j_1},k_{j_1}\mid i$ 且 $\exists k_{j_2},k_{j_2}\mid i-1$。

若只有一对 $k_{j_1},k_{j_2}$，则可以令 $i=ak_{j_1}=bk_{j_2}+1$，有 $ak_{j_1}-bk_{j_2}=1$。由扩展欧几里得相关知识可以求解。

然而，此时有很多对 $k$，只需满足其中之一即可，故不能直接推出形如 $i=ak$ 或 $i=bk+1$ 的性质；若对所有 $k$ 两两之间计算贡献，又会算重。注意到 $m$ 非常小，所以可以对于所有 $k_j$ 枚举是否有 $k_j\mid i$ 或 $k_j\mid i-1$，避免了算重。具体地，对于全集 $U=\{1,2,\dots,m+1\}$ 的子集 $S,V$，记 $f(S,V)$ 为满足 $j\in S\Leftrightarrow k_j\mid i$，$j\in V\Leftrightarrow k_j\mid i-1$ 的 $i$ 的数量，我们可以考虑算出 $\sum_{S\ne\varnothing,V\ne\varnothing}f(S,V)$。

然而，$f(S,V)$ 并不好算，因为即使我们知道了所有 $k_j\mid i$ 是否成立，也与我们能求的“只有一对 $k_{j_1},k_{j_2}$”的情况相去甚远。但注意到如果忽略所有 $k_j\nmid i$ 的限制，即只考虑 $k_j\mid i$，那么 $i$ 受到的限制即为 $\text{lcm}_{j\in S}\{k_j\}\mid i$。记 $K=\text{lcm}_{j\in S}\{k_j\}$，情况转化为只有单个 $K\mid i$ 的情况，是可做的。故考虑容斥。

具体地，记 $h(S,V)$ 为满足 $j\in S\Rightarrow k_j\mid i$，$j\in V\Rightarrow k_j\mid i-1$ 的 $i$ 的数量（注意 $\Rightarrow$ 与 $\Leftrightarrow$ 的区别）。为了辅助，再记 $g(S,V)$ 为满足 $j\in S\Leftrightarrow k_j\mid i$，$j\in V\Rightarrow k_j\mid i-1$ 的 $i$ 的数量。有：

$$\begin{aligned} g(S,V)=&\sum_{V_1\supseteq V}f(S,V_1)\\ \Rightarrow f(S,V)=&\sum_{V_1\supseteq V}(-1)^{|V|-|V_1|}g(S,V_1)\\ \Rightarrow \sum_{V\ne\varnothing}f(S,V)=&g(S,\varnothing)-f(S,\varnothing)\\ =&\sum_{V\ne\varnothing}(-1)^{|V|-1}g(S,V) \end{aligned} $$

同理，

$$\begin{aligned} h(S,V)=&\sum_{S_1\supseteq S}g(S_1,V)\\ \Rightarrow g(S,V)=&\sum_{S_1\supseteq S}(-1)^{|S|-|S_1|}h(S_1,V)\\ \Rightarrow \sum_{S\ne\varnothing}g(S,V)=&h(\varnothing,V)-g(\varnothing,V)\\ =&\sum_{S\ne\varnothing}(-1)^{|S|-1}h(S,V) \end{aligned} $$

故：

$$\begin{aligned} &\sum_{S\ne\varnothing}\sum_{V\ne\varnothing}f(S,V)\\ =&\sum_{S\ne\varnothing}\sum_{V\ne\varnothing}(-1)^{|V|-1}g(S,V)\\ =&\sum_{V\ne\varnothing}(-1)^{|V|-1}\sum_{S\ne\varnothing}g(S,V)\\ =&\sum_{V\ne\varnothing}(-1)^{|V|-1}\sum_{S\ne\varnothing}(-1)^{|S|-1}h(S,V)\\ =&\sum_{S\ne\varnothing,V\ne\varnothing}(-1)^{|S|+|V|}h(S,V) \end{aligned} $$

可以枚举 $S,V$，再用扩展欧几里得算法求出 $h(S,V)$，复杂度 $2^{2m}\log n$。

注意到存在 $j_0$ 满足 $j_0\in S\land j_0\in V$ 时，会推出 $k_{j_0}\mid i\land k_{j_0}\mid i-1$，得 $k_{j_0}\mid 1$，故一定无解，所以可以只枚举与 $S$ 不交的 $V$，复杂度 $3^m\log n$。

---

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
using namespace std;
typedef long long ll;

const int mM=11+2, mS=1<<11|9;
ll exgcd(ll &a, ll &b, ll x, ll y) {
	if(!y) return a=1, b=0, x;
	ll res=exgcd(b, a, y, x%y);
	b-=x/y*a;
	return res;
}

int n, m, k[mM];
int lcm[mS], cnt[mS];
//lcm[s] 表示集合内所有 kj 的 lcm 

int main() {

	scanf("%d%d", &n, &m);
	rep(i, 1, m) {
		scanf("%d", k+i);
	}
	sort(k+1, k+m+1), m=unique(k+1, k+m+1)-k-1;
	k[++m]=n;

	rep(i, 1, m) {
		lcm[1<<i-1]=k[i];
	}
	lcm[0]=1;
	rep(s, 1, (1<<m)-1) {
		cnt[s]=cnt[s>>1]+(s&1);
		const int a=lcm[s&s-1], b=lcm[s&-s], g=__gcd(a, b);
		if(a>n || b>n || (ll) a/g*b>n) lcm[s]=n+1;
		//如果 lcm 过大，一定无解 
		else lcm[s]=a/g*b;
	}
	int ans=0;
	rep(s0, 1, (1<<m)-1) if(lcm[s0]<=n) {
		const ll x=lcm[s0];	//i mod x = 0
		for(int _1=_^s0, s1=_1; s1; s1=_1&s1-1) if(lcm[s1]<n) {
			const ll y=lcm[s1];	//i mod y = 1
			ll a, b, g=exgcd(a, b, x, y), l=x/g*y;
			if(g>1) continue;
			a=(a%y+y)%y;
			assert(a*x%y==1);
			ans+=(cnt[s0]+cnt[s1]&1? -1: 1)*(n/l+(n%l>=a*x));
		}
	}
	printf("%d\n", ans);
	return 0;
}