NOI2010能量采集 题解
读完题之后我们发现在每个产生贡献的点((x1,y1))中，它与原点之间的点((x2,y2))都满足(x2|x1),(y2|y1)。现在我们要求它与原点之间点的个数，也就是这个点((x,y))最大可以被除以多少——肯定是(gcd(x1,y1))啊。
所以我们就知道怎么做啦：(2 imes sum_{i=1}^n imes sum_{j=1}^m imes gcd(i,j)-n imes m)
中间的那个可以用莫比乌斯反演做！
设f(i)表示x,y最大公约数为i的个数。设F(i)表示x,y存在i这个公约数。
因为(f(i)=sum_{i|j} imes F(j))，上限为(min(n,m))
所以(F(i)=sum_{i|j}mu(j/i) imes f(j))
f(i)不太好做，但是F(i)却很容易算出来（具体怎么算大家可以参考HDU GCD这个题）
所以我们预处理出(mu)函数的值，然后按照套路做就可以啦qwq
代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,m,cnt;
int vis[MAXN],mu[MAXN],prime[MAXN];
long long ans;
long long f[MAXN],F[MAXN];
inline void get_mu()
{
vis[1]=mu[1]=1;
for(int i=2;i<=MAXN;i++)
{
if(vis[i]==0) mu[i]=-1,prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=MAXN;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]) mu[i*prime[j]]=-mu[i];
else {mu[i*prime[j]]=0;break;}
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
get_mu();
if(n>m) swap(n,m);
for(int i=1;i<=n;i++) F[i]=1ll*(n/i)*(m/i);
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i)
f[i]+=1ll*mu[j/i]*F[j];
for(int i=1;i<=n;i++) ans+=1ll*f[i]*i;
ans=ans*2-1ll*n*m;
printf("%lld
",ans);
return 0;
}