标签：gcd sum 28 CSP lcm operatorname 模拟

CSP-S 模拟赛 28

T1

• 签到题。对 \(b\) 分解质因数后便容易求解。

T2

• 考虑枚举 \(\gcd(S)\) 的取值 \(x\)，则 \(\operatorname{lcm}(S)=m-x\)。
• 那么同时变形 \(\gcd\) 和 \(\operatorname{lcm}\) 变为 \(\gcd(S)=1,\operatorname{lcm}(S)=\dfrac{m-x}{x}\)。
• 那么对于 \(\gcd\) 和 \(\operatorname{lcm}\) 的取值，有三种情况：

\[f(x)=\sum [\gcd=1,\operatorname{lcm}=x] \]

\[g(x)=\sum [\gcd|x,\operatorname{lcm}=x] \]

\[h(x)=\sum [\gcd|x,\operatorname{lcm}|x] \]

• \(h(x)\) 是简单的。容易知道 \(h(x)=\sum_{d|x}g(d)\)。

• 由莫比乌斯反演，\(g(n)=\sum_{d|n}\mu(d)f(\dfrac{n}{d})\)。

• 那么求出 \(g\) 后从 \(g\) 推到 \(f\) 的式子是同构的。实际上这就是一个容斥的过程。

T3

• 简单题。从左往右和从右往左各做一遍 dp，采用求和优化一下就能过了，虽然理论上时间复杂度不正确。

T4

• 抽象科技题目，咕咕咕~

标签：gcd,sum,28,CSP,lcm,operatorname,模拟
From： https://www.cnblogs.com/Rock-N-Roll/p/18459385