rt，考场上纯对着样例找规律。换了 17 种筛法过后过了这道题。

代码在这里。

void sieve(int n) {
	f[1] = 1;
	vis[1] = 1;
	rep (i, 2, n) {
		if (!vis[i]) {
			p.emplace_back(i);
			f[i] = i + 1;
		}
		for (auto j : p) {
			if (i * j > n) break;
			int pos = i * j;
			vis[pos] = 1;
			f[pos] = f[i] * f[j];
			if (i % j == 0) {
				f[pos] -= f[i / j] * j;
				break;
			}
		}
	}
}

其中 $f_i$ 表示 $i$ 的约数和。