这场比赛我及时的参加了，但是打的时候状态实在是太烂了，只做出来了Div2的AB题。
A Little C loves 3 I
直接构造就行。
B Cover Points
应该很容易就看出来这个等腰三角形的腰是坐标轴，然后就用(y=b-x)的一次函数往上套就行了。
C Enlarge GCD
这个题比赛的时候我交了4次，没有一次想到要先除gcd的。实际上在赛场上我已经接近正解了，就是枚举素因子，然后把最多的那个留着，其他的删掉就好了啊。
好吧，说起来简单，真正要把代码写到AC还是要看std的（摔
话说std的码都好短啊。
Code：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
const int N = 15000000+10;
const int M = 3e5 + 10;
int pri[N], notp[N], sz;
int n, d[N], a[M];
void get_pri() {
notp[1] = 1;
for (int i = 2; i < N; ++i) {
if (!notp[i]) notp[i] = pri[++sz] = i;
for (int j = 1; j <= sz; ++j) {
int k = i * pri[j];
if (k >= N) break;
notp[k] = pri[j];
if (i % pri[j] == 0) break; // 我这里竟然写错了
}
}
}
int gcd(int x, int y) { return !y?x:gcd(y, x%y); }
int main() {
scanf("%d", &n);
get_pri();
int Gcd = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
Gcd = gcd(a[i], Gcd);
}
int ans = 0;
for (int i = 1, x; i <= n; ++i) {
for (int j = a[i]/Gcd; j > 1; )
for (++d[x = notp[j]]; notp[j] == x;) j /= notp[j];
}
for (int i = 1; i < N; ++i) ans = std::max(ans, d[i]);
printf("%d
", !ans ? -1 : n - ans);
return 0;
}
D Little C Loves 3 II
一道鬼畜的找规律的题，有点小凯的疑惑的感觉。这个题没啥意思。
E Region Separation
这个题是一道真正的好题。
首先我们确定这个国家能否被分成(k)个level-2的区域，这其实并不难，设总和为(S)，那么每一块的和应该是(S/k)，我们从叶子节点开始考虑，记一个节点(i)及其子树的和为(S_i)，每次遇到一个(S_i = S/k)的节点就把它和它的子树分出去，这样，我们容易发现，只有(S_i equiv 0 (mod dfrac{S}{k}))的节点有可能被分出去。因此，至少要有(k)个节点满足这个条件才有可能把这个国家分成(k)份。由于所有的数都是正的，所以也可以推出至多有(k)个节点满足这个条件。那么我们就只用考虑有多少个(k)满足这个条件了，化简那个条件可以得到(k)是(dfrac{S}{gcd (S, S_i)})的整数倍（这个有点靠直觉），然后就能DP求(k)是否是一个合法的解。
然后就可以得出这样的结论：level-i可以被划分为(k_i)个部分当且仅当level-2可以被划分为(k_i)个部分且(k_{i-1}mid k_i)（这里稍微有点绕，就是要注意每层的每个区域的权值和相等这个条件），然后就可以DP了，设(F_i)为最后一层有(i)个区域的方案数，通过枚举(i)的倍数来转移就好了。
Code:
#include <cstdio>
typedef long long LL;
const int N = 1e6 + 10;
const LL MOD = 1e9 + 7;
int n, fa[N];
LL s[N], f[N], F[N];
LL gcd(LL x, LL y) { return !y?x:gcd(y, x%y); }
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &s[i]);
for (int i = 2; i <= n; ++i) {
scanf("%d", &fa[i]);
}
for (int i = n; i; --i) s[fa[i]] += s[i];
for (int i = n; i; --i) {
LL x = s[1] / gcd(s[1], s[i]);
if (x <= n)
++f[x];
}
for (int i = n; i; --i) {
for (int j = i; (j+=i) <= n; ) f[j] += f[i];
}
F[1] = 1;
LL ans = 0;
for (int i = 1; i <= n; ++i) {
if (f[i] == i) {
ans = (ans + F[i]) % MOD;
for (int j = i; (j+=i) <= n; ) F[j] = (F[j] + F[i]) % MOD;
}
}
printf("%lld
", ans);
return 0;
}