bzoj 2820.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#define intl long long
#define maxn 10000100
#define N 10000000
using namespace std;
int i,j,k,l,m,n,top,t,T,a,b;
int pri[maxn],mu[maxn],mark[maxn];
intl g[maxn],ans;
int main() {
	freopen("2820.in","r",stdin);
	freopen("2820.out","w",stdout);
	for (i = 2; i <= N; i++) {
		if (!mark[i]) {
			pri[++top] = i;
			mu[i] = -1;
			g[i] = (intl) 1;
		}
		for (j = 1; j <= top && i * pri[j] <= N; j++) {
			mark[i * pri[j]] = 1;
			if (i % pri[j]) {
				mu[i * pri[j]] = -mu[i];
				g[i * pri[j]] = (intl) mu[i] - g[i];
			}
			else {
				g[i * pri[j]] = (intl) mu[i];
				break;
			}
		}
	}

	for (i = 3; i <= N; i++) g[i] += g[i - 1];
	scanf("%d",&T);
	for (; T; T--) {
		scanf("%d %d",&n,&m);
		ans = 0;
		for (t = 1; t <= min(n,m);) {
			a = n / t; b = m / t;
			k = min(n / a,m / b);
			ans += (intl) a * (intl) b * (g[k] - g[t - 1]);
			t = k + 1;
		}
		printf("%lld\n",ans);
	}

	return 0;
}