【BZOJ3518】点组计数

Description

    平面上摆放着一个n*m的点阵（下图所示是一个3*4的点阵）。Curimit想知道有多少三点组(a，b，c)满足以a，b，c三点共线。这里a，b，c是不同的3个点，其顺序无关紧要。(即(a，b，c)和(b，c，a)被认为是相同的）。由于答案很大，故你只需要输出答案对1，000，000，007的余数就可以了。

Input

有且仅有一行，两个用空格隔开的整数n和m。

Output

有且仅有一行，一个整数，表示三点组的数目对1，000，000，007的余数。（1，000。000。007是质数）

Sample Input

3 4

Sample Output

2 0

HINT

对于100%的数据，1< =N．m< =50000

题解：我们先不考虑水平的和竖直的点组，并且先只考虑形如 / 的点组（形如 \ 的点组数目相同）。考虑枚举两端的点的相对位置，将其看成向量(i,j)。如果(i,j)确定了，则中间的点可能的位置也就确定了，并且左端点的绝对位置也能确定了。说白了，方案数等于如下式子：

$\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}^mgcd(i,j)(n-i)(m-j)\\=\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)$

由于n,m很小，暴力算即可。

 

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=50010;typedef long long ll;const ll P=1000000007;int num;ll n,m,ans;int pri[N],phi[N];bool np[N];int main(){	scanf("%lld%lld",&n,&m);	if(n>m)	swap(n,m);	int i,j;	phi[1]=1;	for(i=2;i<=n;i++)	{		if(!np[i])	pri[++num]=i,phi[i]=i-1;		for(j=1;j<=num&&i*pri[j]<=n;j++)		{			np[i*pri[j]]=1;			if(i%pri[j]==0)			{				phi[i*pri[j]]=phi[i]*pri[j];				break;			}			phi[i*pri[j]]=phi[i]*(pri[j]-1);		}	}	for(i=1;i<=n;i++)	ans=(ans+phi[i]*((n-i+n%i)*(n/i)/2%P)%P*((m-i+m%i)*(m/i)/2%P)%P)%P;	ans=(ans-((n-1)*n/2%P)*((m-1)*m/2%P)%P+P)%P;	ans=(ans<<1)%P;	ans=(ans+n*(m*(m-1)*(m-2)/6%P)%P+m*(n*(n-1)*(n-2)/6%P)%P)%P;	printf("%lld",ans);	return 0;}