Virtual Participated on May 24, 2020.

VP available here: Virtual Judge

Practice available on HDOJ.

• Solved 6 out of 11 problems
• Rank 27/532 in official records
• Solved 6 out of 11 afterwards

(√ for solved during VP, ○ for after VP, - for tried but not solved)

• Solved by Pantw

给一个边权两两不同的无向图。求最小生成树，以及最小生成树中使得所有点对最短路平均值的最小值。

$n\le 10^5, m\le 10^6$。

由于边权不同我们可以直接知道最小生成树是唯一的，那么求出来之后 DP 一下即可。

• Idea by Pantw, Withinlover, Gary
• Debug by Pantw, Withinlover, Gary
• Code by Pantw

$n\times 20$ 的棋盘，有若干相同的棋子，每个格子上至多有一个棋子，移动方式是：

• 若一个棋子右边是空格子，那么它可以移动到该格子；
• 若一个棋子隔着连续的一堆棋子，那么它可以跳过这些棋子，达到右边的第一个空格。
• 棋子不能超出右边界。

给定初始状态，问先手必胜还是先手必败。

由于 $20\times 2^{20}$ 不大，可以直接预处理出 SG 函数值。

然后就是经典的 Nim 游戏了。

• Idea by Pantw
• Code by Withinlover

给定一个数列，每次查询一个区间 $[l, r]$。输出区间的最大公约数 $x$，同时输出满足最大公约数为 $x$ 的区间 $[l', r']$ 的个数。

区间公约数查询是裸的ST表。预处理后直接回答。

针对第二问，可以发现最大公约数的取值不会太多。且固定 $l$ 时，$\gcd(a_l,a_{l+1},\dots,a_r)$单调递减，可以二分确定出每一次 $\gcd$ 变化的位置，然后用一个 $map$ 存一下。就做完了。

简易证明：考虑将 $a_l$ 质因数分解，易知当 $r$ 变化时， $\gcd$ 的值最多会下降其质因数个数次。

• Idea by Withinlover, Pantw
• Code in practice by Withinlover

已知三个正整数 $n, m, p$，其中 $n$ 不含平方因子。

设 $k=\sum_{i=1}^{m}\varphi(i*m) \bmod {1000000007}$；

计算 $ans = k^{k^{k^{k\dots}}}\bmod p$，$k$ 有无限个。

大力推公式，设 $F(n, m) = \sum_{i=1}^m\varphi(i*n)$

$$F(n,m)=\sum_{i=1,i\%p!=0}^m\varphi(i*n)+\sum_{i=1,i\%p==0}^m\varphi(i*n)$$ $$=\varphi(p)\sum_{i=1,i\%p!=0}^m\varphi\left(i*\frac{n}{p}\right)+p\sum_{i=1,i\%p==0}^m\varphi\left(i*\frac{n}{p}\right)$$ $$=\varphi(p)\sum_{i=1}^m\varphi\left(i*\frac{n}{p}\right)+\sum_{i=1,i\%p==0}^m\varphi\left(\frac{i}{p}*n\right)$$ $$=\varphi(p)\sum_{i=1}^m\varphi\left(i*\frac{n}{p}\right)+\sum_{i=1}^{m/p}\varphi\left(i*n\right)$$ $$=\varphi(p)F\left(\frac{n}{p},m\right) + F\left(n,\frac{m}{p}\right)$$

第一个难题解决，注意下递归的边界就可以做了。

计算 $ans$ 时，迭代使用欧拉定理，$A^B\bmod C=A^{B\%\varphi(C)+\varphi(C)}\bmod C$，显然会很快收敛为 $0$，后面的无限多个 $k$ 就没有意义了。迭代计算即可。