【BZOJ 2820】YY的GCD

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2820
离线版题目：http://paste.ubuntu.com/20287584/

这个东西嘛，如果没有多组询问的话，枚举质数就可以水过去
但有多组询问QAQ
前排膜拜hzwer：http://hzwer.com/6142.html
现在身心俱疲，什么都不想说了 累…..

#include<iostream>
#include<cstdio>
#include<bitset>
#define LL long long
using namespace std;

const int MAXN = 10000000+9;
const int MX = 10000000;

int pri[MAXN],tot,fuc[MAXN],mu[MAXN];
bitset<MAXN> tag;

inline void Get_Fuc(){
	fuc[1] = 0;
	for (int i=2;i<=MX;i++){
		if (!tag[i]) pri[++tot] = i, fuc[i] = 1, mu[i] = -1;
		for (int j=1;j<=tot && i*pri[j]<=MX;j++){
			tag[i*pri[j]] = 1;
			if (i % pri[j]) fuc[i*pri[j]] = -fuc[i] + mu[i], mu[i*pri[j]] = -mu[i];
			else {fuc[i*pri[j]] = mu[i]; mu[i] = 0; break;}
		}
	}
	for (int i=2;i<=MX;i++) fuc[i] += fuc[i-1];
}

int main(){
	Get_Fuc(); int T; cin>>T;
	while (T--) { LL vout = 0;
		int n,m,tmp; scanf("%d%d",&n,&m);
		if (n > m) swap(n,m);
		for (int i=1;i<=n;i=tmp+1){
			tmp = min(n/(n/i),m/(m/i));
			vout += (LL)(fuc[tmp]-fuc[i-1])*(n/i)*(m/i);
		}
		printf("%lld\n",vout);
	}
	return 0;
}