【BZOJ 2005】[Noi2010] 能量采集

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

这题，O（n^0.5+n）的做法我不会QAQ
%JCVB，看了半小时，还是不懂QAQ
只会O(n^1.5+n)的做法：
枚举gcd(i,j)的值，然后就和“Zap”一样了
居然没有T，好感动இ௰இ

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

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

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

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

int main(){
	Get_mu(); int n,m,a,b,tmp;LL vout=0;
	scanf("%d%d",&n,&m); if (n > m) swap(n,m);
	for (int k=1;k<=n;k++) {
		a = n/k; b = m/k;
		for (int i=1;i<=a;i=tmp+1){
			tmp = min(a/(a/i),b/(b/i));
			vout += (LL)k*(sum[tmp]-sum[i-1])*(a/i)*(b/i);
		}
	}
	printf("%lld\n",vout*2-(LL)n*m);
	return 0;
}