T1
题面：一个长度为 \(n\) 的序列 \(\{a_1,a_2,\cdots,a_n\}\)，求有多少个不同的 \(\gcd(a_i,a_j)(i\not=j)\)。 \(n\le2\times 10^5,a_i\le 10^7\)
题解：从大到小枚举值域，简单容斥，复杂度是调和级数 \(O(n\ln n)。\)
死亡回放：\(N\) 开小了。
核心代码
for (int s = maxa; s >= 1; s--) {int now = 0;for (int i = s; i <= maxa; i += s) now += vis[i];cnt[s] = 1ll * now * (now - 1) >> 1; for (int i = 2 * s; i <= maxa; i += s) cnt[s] -= cnt[i];if (cnt[s]) ans++;
}
T3
题面：三维空间中有 \(n\) 个点，\(n\) 个向量，你要给每个点分配一个向量，使得分配后每两个点之间的距离 \(\ge\) 原来两个点距离，输出分配方案。
\(n\le 500\)，\(-10^{4}\ge\)每个点和向量的坐标大小 \(\le 10^4\)。
题解：考虑动态调整，给每个点先分配一个向量。然后 \(O(n^2)\) 的枚举两个点，如果两个点之间的距离 \(\le\) 原来的距离，进行交换，在重新从头枚举，重复执行，知道满足条件。
核心代码
random_shuffle(p + 1, p + n + 1);
// for (int i = 1; i <= n; i++) cout << p[i] << " \n"[i == n];
while (1) {bool flag = 0;for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++)if (disa(i, j) > dis(i, j)) {swap(p[i], p[j]);flag = 1;}if (!flag) break;
}