bzoj2005 [NOI2010]能量采集莫比乌斯反演

本文主要是介绍bzoj2005 [NOI2010]能量采集莫比乌斯反演，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门

考虑点 $(x, y)$ 对答案的贡献：
设 $g c d (x, y) = k$ ， $x = a k, y = b k .$
若有 $x^{'}, y^{'}$ 满足 $(x^{'}, y^{'})$ 在 $(0, 0)$ 到 $(x, y)$ 的直线上，则有 $\large\frac{y'}{x'}=\frac{y}{x}=\frac{b}{a}$
则 $(x^{'}, y^{'})$ 珂以取的值为： $(a, b), (2 a, 2 b), . . ., ((k - 1) a, (k - 1) b)$
所以 $(0, 0)$ 到 $(x, y)$ 共有 $k - 1$ 个点，即 $g c d (x, y) - 1$ 个点qwq。
所以答案变成：
$ans=\Large\Sigma\large_{i=1}^{N}\Large\Sigma\large_{j=1}^M(2(gcd(i,j)-1)+1)$
$=2\Large\Sigma\large_{i=1}^N\Large\Sigma\large_{i=1}^Mgcd(i,j)-N*M$
调换一下枚举顺序，珂以得到 $ans=2\Large\Sigma\large_{t=1}^{min(N,M)}t(\Large\Sigma\large_{i=1}^N\Large\Sigma\large_{j=1}^M[gcd(i,j)==t])-N*M$
对这坨东西大莉莫比乌斯反演，乱搞一波（乱搞过程：蒟蒻的博客qwq）
得到 $ans=\Large\Sigma\large_{t=1}^{min(N,M)}(t\Large\Sigma\large_{t|d}\mu(\frac{d}{t})\lfloor\frac{N}{d}\rfloor\lfloor\frac{M}{d}\rfloor)-N*M$
然后每次大莉枚举 $t$ ，对括号里的部分大莉枚举 $t$ 的倍数即可。
珂以证明这样时间复杂度是 $O (n l o g n)$ 的qwq
话说这道题好像还有一个查询只用 $O(\sqrt n)$ 的神仙做法……比较玄学qwq

毒瘤代码

#include<stdio.h>
#include<cstring> 
#include<algorithm>
#define re register int
#define rl register ll
using namespace std;
typedef long long ll;
int read() {re x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-')	f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=10*x+ch-'0';ch=getchar();}return x*f;
}
const int Size=100005;
int tot,prime[Size],mu[Size];
bool vis[Size];
void getp(int maxn) {mu[1]=1;for(re i=2; i<=maxn; i++) {if(!vis[i]) {prime[++tot]=i;mu[i]=-1;}for(re j=1; j<=tot && i*prime[j]<=maxn; j++) {vis[i*prime[j]]=true;if(i%prime[j]==0)	break;mu[i*prime[j]]=-mu[i];}}
}
int main() {int n=read();int m=read();int minn=min(n,m);getp(minn);ll ans=0;for(re t=1; t<=minn; t++) {int lst;ll sum=0;for(re i=t; i<=minn; i+=t) {sum+=(ll)mu[i/t]*(n/i)*(m/i);}ans+=sum*t;}printf("%lld",(ans<<1ll)-(ll)n*m);return 0;
}