这是一道“约数容斥”的模板题。 思路 首先先不管 $\frac{x}{g}\ne 1,\frac{y}{g}\ne 1$ 这条限制。有 gcd 的计数题的常见技巧是考虑不同的 gcd 对于答案的贡献。…

第一类斯特林数 定义：将 $n$ 个不同元素划分进 $m$ 个相同的环（不可为空）的方案数，记为 $S_1(n,m)$ 或 ${n\brack m}$（{n\brack m}）。其中“环”指“旋转后重…

定义 本文中默认将正整数 $n$ 分解质因数得到 $n=\prod_{i=1}^{m} p_i^{c_i}$。 莫比乌斯函数的定义为： μ(n)={1n=10∃i,ci≥2(−1)m∀i,ci=1\m…

首先我们将题面翻译成数学语言，即给定 $n,k(1\le k\le n\le 10^5$，求从 $n$ 个人里选 $k$ 个人，再从这 $k$ 个人里选出任意多个人，再从这任意多个人里选出一个人的方案…