BZOJ 3518 点组计数

题目大意

求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m(\gcd(i,j)-1)(n-i)(m-j)$.

这题求的就是这东西= =

把1去掉之后进行反演：

$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\gcd(i,j)(n-i)(m-j)\ = \sum\limits_{i=1}^n\sum\limits_{j=1}^m (n-i)(m-j)\gcd(i,j)\ = \sum\limits_{i=1}^n\sum\limits_{j=1}^m (n-i)(m-j) \sum\limits_{d|\gcd(i,j)}\varphi(d)\=\sum\limits_{d=1}^n \varphi(d)\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}(n-i\times d)\sum\limits_{j=1}^{\lfloor \frac{m}{d}\rfloor} (m-j\times d)$

后面两个是等差数列，第一个可以暴力枚举，搞定。

#include <cstdio>
#include <algorithm>
using namespace std;
#define R register
#define MO 1000000007
long long prm[100000],phi[100000];
bool v[100000];
int main()
{
	R long long n,m,cnt=0,ans=0;
	scanf("%lld%lld",&n,&m);
	if(n>m) swap(n,m);
	phi[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!v[i]) prm[++cnt]=i,phi[i]=i-1;
		for(int j=1;j<=cnt&&i*prm[j]<=n;++j)
		{
			v[i*prm[j]]=true;
			if(i%prm[j]) phi[i*prm[j]]=phi[i]*phi[prm[j]];
			else
			{
				phi[i*prm[j]]=phi[i]*prm[j];
				break;
			}
		}
	}
	for(int d=1;d<=n;++d) ans=(ans+phi[d]*((((n-d+(n-(n/d)*d))*(n/d))/2)%MO*(((m-d+(m-(m/d)*d))*(m/d))/2)%MO))%MO;
	ans=(ans-((1ll*m*(m-1)*n*(n-1)/4)%MO)+MO)%MO;
	ans=(ans<<1)%MO;
	ans=(ans+(1ll*n*(n-1)*(n-2)*m/6)%MO+(1ll*m*(m-1)*(m-2)*n/6)%MO)%MO;
	printf("%lld\n",ans);
	return 0;
}