BZOJ2401 陶陶的难题I

推了半天，发现还是得sqrt，过不到啊。

然后发现与经典的问题相比，就是n=n。然后这不是做过的那个LCM sum的前缀和就完了嘛。傻了。

然后第一次MLE是因为明明压了8位，还是开了30长的数组。第二次WA是因为高精输出的时候%08d写成了%8d。是不是明天又要逗极而死了。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long dint;

#define _l (long long int)

const int maxlen = 7;
const dint base = 1e8;
struct BigInt {
	dint dig[maxlen], len;
	BigInt() {
		len = 0;
	}
	void set(dint x) {
		dig[0] = x;
		len = 1;
		while (dig[len - 1] >= base) {
			dig[len] = dig[len - 1] / base;
			dig[len - 1] %= base;
			++ len;
		}
	}
	void copy(const BigInt& x) {
		len = x. len;
		for (int i = 0; i < len; ++ i)
			dig[i] = x. dig[i];
	}
	void inc(dint x) {
		if (!len) {
			dig[0] = x;
			len = 1;
		}
		else
			dig[0] += x;
		for (int i = 0; i < len - 1 && dig[i] >= base; ++ i) {
			dig[i + 1] += dig[i] / base;
			dig[i] %= base;
		}
		while (dig[len - 1] >= base) {
			dig[len] = dig[len - 1] / base;
			dig[len - 1] %= base;
			++ len;
		}
	}
	void print() {
		printf("%d", (int)dig[len - 1]);
		for (int i = len - 2; i >= 0; -- i)
			printf("%08d", (int)dig[i]);
		putchar(10);
	}
};

const int maxn = 1000009;

int tp, pn[maxn], phi[maxn];
dint tot[maxn];
BigInt ans[maxn];
bool pr[maxn];

void pre(int n) {
	memset(pr, 0, sizeof(pr));
	tp = 0;
	phi[1] = 1;
	for (int i = 2; i <= n; ++ i) {
		if (!pr[i]) {
			pn[tp ++] = i;
			phi[i] = i - 1;
		}
		for (int j = 0, t; j < tp && (t = i * pn[j]) <= n; ++ j) {
			pr[t] = 1;
			if (i % pn[j])
				phi[t] = phi[i] * phi[pn[j]];
			else {
				phi[t] = phi[i] * pn[j];
				break;
			}
		}
	}
	for (int i = 1; i <= n; ++ i) {
		dint d = (i == 1) ? 1 : (_l i * phi[i] >> 1);
		for (int j = 1, t; (t = j * i) <= n; ++ j)
			tot[t] += d;
	}
	ans[1]. set(1);
	for (int i = 2; i <= n; ++ i) {
		tot[i] = tot[i] * i;
		ans[i]. copy(ans[i - 1]);
		ans[i]. inc(tot[i] * 2 - i);
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	int t;
	scanf("%d", &t);
	pre(1e6);
	while (t --) {
		int n;
		scanf("%d", &n);
		ans[n]. print();
	}
}