[bzoj 2154] Crash的数字表格

求. (n,m ≤ 10^7) 等于某个定值的限制不好搞, 但是某定值的倍数比较容易处理. 令 则 反演一下, 令, 并代回原式 枚举商分段计算即可.

没有特殊的常数优化是跑不了一千万的......NOIP蚯蚓那题没能给我深刻的教训 QAQ

用积分估计一下时间复杂度, . 计算和式的部分的复杂度可能低于, 但是不会算......

typedef long long ll;
const int MOD = 20101009, QUARTER = 15075757, N = 1e7;
short mu[N + 1];
int sum[N + 1];

void sieve(int n)
{
	static bool notPrime[N + 1];
	static int prime[N + 1];
	int cnt = 0;
	sum[1] = mu[1] = 1;
	For (i, 2, n) {
		if (!notPrime[i]) {
			prime[cnt++] = i;
			mu[i] = -1;
		}
		for (int j = 0, x, p; j < cnt && (x = i*(p = prime[j])) <= n; ++j) {
			notPrime[x] = true;
			if (i % p)
				mu[x] = -mu[i];
			else
				break;
		}
		sum[i] = (sum[i-1] + (ll)i*i*mu[i] % MOD + MOD) % MOD;
	}
}

int f(int n, int m)
{
	ll ans = 0;
	for (int i = 1, j; i <= n; i = j+1) {
		int _n = n/i, _m = m/i;
		j = min(n, min(n/_n, m/_m));
		(ans += (ll)(sum[j] - sum[i-1] + MOD) * _n % MOD * (1+_n) % MOD * _m % MOD * (1+_m) % MOD) %= MOD;
	}
	return (ans * QUARTER) % MOD;
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	if (n > m) swap(n, m);
	sieve(n);
	ll ans = 0;
	for (int i = 1, j; i <= n; i = j+1) {
		int _n = n/i, _m = m/i;
		j = min(n, min(n/_n, m/_m));
		(ans += (ll)(i+j)*(j-i+1)/2 % MOD * f(_n, _m)) %= MOD;
	}
	printf("%lld\n", ans);
	return 0;
}