标签：秋季 gcd 题解 sum 2024 lcm operatorname 模拟

2024 秋季模拟赛题解

CSP-S 模拟赛

2024.9.8 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

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

2024.9.15 CSP-S 模拟赛 29

T1

• \(n\le 18\) 显然是状压 dp。
• 考虑设状态 \(dp_{i,j}\) 表示状态为 \(i\)，最终的 \(a\) 为 \(j\) 时的最大代价及方案数。转移是简单的。
• 优化是观察到最终的 \(a\in(\max a_i,\max a_i+1)\)。那么这一维便可以用 \(0/1\) 来设。

标签：秋季,gcd,题解,sum,2024,lcm,operatorname,模拟
From： https://www.cnblogs.com/Rock-N-Roll/p/18425927