Day2
\(100+96+60+70=326,rk1\)
T1
- 签到题
- 暴力
T2
- 莫比乌斯反演题
- 首先容易想到枚举最大公约数是多少，不妨设枚举的 \(\gcd=g\) ，则我们可以开一个桶 \(b_i\) 表示 \(i\) 倍数的数有多少个
- 对于每个固定的 \(g\) 答案为 \(\large \sum\limits_{i=1}^{A} \mu(i) \binom{b_{i \times g}}{\frac{k}{g}}\) ，复杂度 \(O(n \log n)\) ，不过是严格小于的。
T3
- 猜结论题。
- 把图给画出来，发现没有什么性质。说明这个图的性质就是非常稠密
- 这题从每个点的扩展次数 \(\leq \log_3 mod\) ，因此考虑 meet in the middle
- 注意对于第三个操作可以找到他的 \(31\) 次剩余
T4
- 正睿题
- 翻折容斥即可
- 多项式优化不会