Codeforces Round #372 (Div. 2)
C. Plus and Square Root
题意
- 一个游戏中，有一个数字\(x\)，当前游戏等级为\(k\)，有两种操作：
- '+'按钮：使得\(x=x+k\)
- '√'按钮：使得\(x=\sqrt{x}\)，此时\(x\)必须是平方数，游戏等级加1，即\(k=k+1\)，且\(\sqrt{x}\)是\(k+1\)的倍数。
- 游戏开始时，\(x=2,k=1\)，输出\(n(n \le 10^5)\)个数，表示每个等级对应的\(\frac{x}{k}\)值(就是倍数)，并且输出的值不超过\(10^{18}\)。
-
任意时刻，\(x\)必须是\(k\)的倍数。
Additionally, after each move, if ZS the Coder is at level k, and the number on the screen is m, then m must be a multiple of k.
思路
- 设\[x=kp=(k+1)^2q^2\]
- 则\[p=\frac{(k+1)^2q^2}{k}\]
如果令\(q=k\)，得\[p=k(k+1)^2\]
这样的倍数显然满足题意。
代码
D. Complete The Graph
题意
- 一张图有\(n(n \le 10^3)\)个点，\(m(m \le 10^4)\)条边。
- 每条边有权值（均为正整数），当边权为0时，表示需要重新赋值，使得\(s \to t\)的最短路径长为\(L(L \le 10^9)\)。
- 若存在一种方案，输出"YES"和所有边的边权；否则输出"NO"。
思路
- 是否存在可以通过极端情况判断，即将所有0边赋值为1以及全赋值为L。
- 若存在，显然可以二分出权值\(x\)，使得所有0边均赋值为\(x\)时，\(s \to t\)的最短路刚好大于或等于\(L\)。
- 此时我们可以通过将某些边从\(x\)变成\(x-1\)使得最短路变成\(L\)，这样的时间复杂度为\(O(NM\log{N})\)，是可以解决的。
- 题解提到了一种复杂度更优的做法，大概思想是二分找到第一条0边，使得最短路小于\(L\)，找到后再二分该边的权值，使得最短路刚好为\(L\)。
代码
E. Digit Tree
题意
- 给一棵树，有\(n(n \le 10^5)\)个点。
- 边有权值\(w_i(1 \le w_i \le 9)\)。
- 求路径\((u,v)\)使得\(u \to v\)路径构成的大数模\(m\)为0，其中\(gcd(10, m) = 1\)。
思路
- 点分治
- 根据欧拉定理\[x^{\phi{(m)}}\equiv 1(mod \verb' 'm), gcd(x, m)=1\]可以求出10的逆元。
代码