【BZOJ】2693: jzptab

http://www.lydsy.com/JudgeOnline/problem.php?id=2693

题意：求$sum_{i=1}^{n} sum_{j=1}^{m} lcm(i, j)$, $n,m le 1e7$, 多个询问$q le 10000$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e7+10, MD=100000009;
int p[N], pcnt, mx;
bool np[N];
ll g[N];
void init() {
	g[1]=1;
	int i, j, t;
	for(i=2; i<=mx; ++i) {
		if(!np[i]) p[++pcnt]=i, g[i]=1-i;
		for(j=1; j<=pcnt; ++j) {
			t=p[j]*i; if(t>mx) break;
			np[t]=1;
			if(i%p[j]==0) { g[t]=g[i]; break; }
			g[t]=g[i]*(1-p[j]);
		}
	}
	for(i=2; i<=mx; ++i) g[i]*=i;
	for(i=1; i<=mx; ++i) g[i]+=g[i-1], g[i]%=MD;
}
int nn[10005], mm[10005];
int main() {
	int t; scanf("%d", &t);
	for(int i=1; i<=t; ++i) scanf("%d %d", &nn[i], &mm[i]), mx=max(max(nn[i], mm[i]), mx);
	init();
	for(int k=1; k<=t; ++k) {
		int n=nn[k], m=mm[k]; if(n>m) swap(n, m);
		ll ans=0, t1, t2;
		for(int i=1, pos=0; i<=n; i=pos+1) {
			pos=min(n/(n/i), m/(m/i));
			t1=((ll)(n/i)*(n/i+1)/2)%MD;
			t2=((ll)(m/i)*(m/i+1)/2)%MD;
			ans+=((g[pos]-g[i-1])*((t1*t2)%MD))%MD;
			ans%=MD;
		}
		printf("%lld
", ((ans%MD)+MD)%MD);
	}
	return 0;
}

　　

题解：参见上一题，bzoj2154 http://www.cnblogs.com/iwtwiioi/p/4268926.html