Codeforces Round #818 (Div. 2)

赛时：476+904+1176+930+0+0

补题：476+904+1176+930+600+0

A. Madoka and Strange Thoughts

求满足 \(a,b\leq n\) 且 \(\frac{lcm(a,b)}{gcd(a,b)}\leq 3\) 的个数。 \(n\leq 10^8,t\leq 10^4\) 。

赛时打表 \(1\) 分钟看出规律，设差分序列 \(b_i=a_i-a_{i-1}\) ，则有 \(b\) 序列按照 \(\{3,3,3,1,5,1\}\) 的循环节循环，那么答案就是 \(\text{整循环节数}\times 16\) 加上剩下的部分。

正解：根据一系列证明得到答案新增一个数 \(x\) ，只有 \((x,x),(x,2x),(x,3x)\) 符合条件，所以需要判断 \([1,n]\) 中整除 \(2/3\) 的所有数，因为可逆，所以答案为 \(n+2\times(\lfloor\frac{n}{2}\rfloor+\lfloor\frac{n}{3}\rfloor)\) 。

B. Madoka and Underground Competitions

构造一个 \(n\times n\) 的图，使得每个 \(1\times k\) 和每个 \(k\times 1\) 的方格中至少有一个 X 且总的 X 个数最少。保证 \(n\bmod k=0\) ，并指定 \((r,c)\) 上一定为 X 。\(1\leq k\leq n\leq 500,1\leq r,c\leq n\) , \(t\leq 100,\sum n\leq 500\) 。

首先贪心的考虑一个 \(k\times k\) 的问题，然后将同样的构造方法放在其他 \(k\times k\) 的图上，这样能够保证正好每 \(k\times 1\) 和 \(1\times k\) 的方格中有 \(1\) 个 X 。那么将 \((r,c):=(r\bmod (n-1),c\bmod (n-1))\) ，其他格贪心取即可，根据感觉可知一定存在构造方案使得正好 \(k\) 个 X 能填满 \(k\times k\) 的图，那么这样一定是最少的。

C. Madoka and Formal Statement

给定首尾相接的数列 \(a,b\) ，若 \(a_i\leq a_{i+1}\) 可以使 \(a_i++\) ,求是否有方案使 \(a\) 经过多次操作后变为 \(b\) 。 \(n\leq 2\times 10^5,a,b\leq 10^9\) ， \(t\leq 10^4,\sum n\leq 2\times 10^5\) 。

这是个贪心，首先判断特殊情况 \(a_i>b_i\) ，直接输出 NO 。其次，若所有的 \(i\) 满足 \(a_i=b_i\,\,||\,\,b_i\leq b_{i+1}+1\) 则一定有解。（考场上我花 \(20\,min\) 想原因）

D. Madoka and The Corruption Scheme

在完全二叉树上每个节点选 \(1\) 个儿子作为 \(winner\) ，并将叶子节点编号为 \(1\sim 2^n\) ，求一种策略，使得在此策略基础上改动至多 \(k\) 个 \(winner\) 后从根节点一直走 \(winner\) 到达的叶子的编号的最大值最小化，求最小值 \(\bmod 10^9+7\) 。 \(n\leq 10^5,k\leq\min(2^n-1,10^9)\) 。

设从根到叶子上非 \(winner\) 边等于 \(k\) 的点的数量为 \(f(k)\) 。

首先要意识到很关键的一点：最小化的值其实是从根到叶子上非 \(winner\) 边小于等于 \(k\) 的点中点值最大的，又因为放点的策略是自己选，所以其实就是要求 \(\sum_{i=1}^kf(i)\) 。

然后再考虑如何求，可以发现无论如何改变 \(winner\) ，都不会使 \(f\) 函数发生任何变化，所以深挖性质后发现 \(f(i)=C_n^i\) ，所以最后答案是 \(\sum_{i=1}^kC_n^i\) 。在预处理 \(inv\) 之后时间复杂度为 \(O(n)\) （但我懒，所以用费马小定理写的逆元，成为瓶颈，是 \(O(n\log (10^9+7))\) ）。

E. Madoka and The Best University

给定 \(n\) ，求 \(\sum_{a+b+c=n}\text{lcm}(c,\gcd(a,b))\bmod(10^9+7)\) 。

\(\gcd(a,b)=\gcd(a,a+b)=\gcd(a,n-c)\) ，设 \(d=\gcd(a,n-c)\) ，那么答案就变成了 \(\sum_c\text{lcm}(c,d)\) 。

枚举 \(c\) ，由于那么对于每个 \(d\) 都有 \(\varphi(\frac{n-c}{d})\) 个答案，前提是 \(d|n-c\) 。

所以可以反向枚举，对于每个 \(d\) 枚举其倍数 \(c\) ，统计答案就是 \(\sum\text{lcm}(c,d)\times\varphi(\frac{n-c}{d})\) 。