现在很晚了，但是这个神必题卡了我真的好久好久。。。。。(before noi until present)......... （你可以通过我被这个SB题卡发现我真是个菜B) 题意 题解 显然 naive 的连边，如果 \(\gcd(a_i,a_j)\),\(a_i \rightarrow b_j\) 那么如果选 \(a_i\) 必须不能选 \(a_j\) ,显然应该选 \(b_j\) 。

分享一点 OI 相关想法。 本来打算这篇文章是面向同学，大家写的，可是鄙人实在是文笔不济，想了想，还是以这样一种说闲话的方式写一些吧。

题意： 你有一个随机数生成器，最初给定一个 \(0\leq x\leq n-1\) 的整数作为随机种子. 这个随机数生成器会每次输出 \(x\) 并将 \(x^k \bmod n\) 作为新的 \(x\)。 你很快发现这个随机数生成器很渣。为了证明它很渣，你想要求出有多少个随机种子，使得这个随机数生成器会输出初始种子无穷多次。

题意 Link sol 贪心思路显然，我们先把选一定没事的放在后面，接下来化归成子问题。 什么时候选一定没事，也就是 \(a_i\) 具有一个质因子 \(p\),使得 \(p\) 在 \(a_i\) 中次数最高。 形式化表示：设 \(a_i=\prod_{k}p_k^{\alpha_{i,k}}\)。 那么 \(a_i\) 选一定没事，当且仅当 存在 \(k\) , \(\fora

题意 Link 题解 答案显然具有单调性。 二分，对于 \(mid\) 我们计算最少需要几个点使得可以全部覆盖整个树。 我们有一个显然的贪心，对于以 \(u\) 为跟的子树，我们选 \(u\) 当且仅当子树内最深的到 \(u\) 的距离恰好为 \(mid\)。 如何证明？ 考虑如果不是这样，我们找到最深的一个选的 \(u\) 不满足上述贪心策略。 跳 \(u\) 父亲，

题意很简洁。 让你求有多少个长度为 \(N\) 的序列 \(A\)，使得 \(\sum_{i=1}^{n}A_i=m,\sum_{\oplus}A_i=0\).

通过 arc123D 讨论一下 \(\texttt{slope trick}\)。

Links

题意 Link

cf 1515F 题意 Link