P3166 [CQOI2014]数三角形

传送门

可以考虑容斥，用三个点的总方案减去三点共线的情况。总的点数为(t=(n+1)*(m+1))，那么总方案数就是(C_t^3)

考虑三点共线，我们枚举这条线段的两个端点((a,b),(x,y))，那么这条线段上的整点数就是(gcd(x-a,y-b)-1)

然而这样复杂度太高。我们考虑优化，把((a,b))给移到原点，那么((x,y))变成((x-a,y-a))，我们可以考虑枚举这个记做((i,j))，然后发现有很多条线段都可以平移成这样，总的条数为((n-i+1)*(m-j+1))

以上只是斜率大于等于(0)的情况。不难发现每一条斜率小于(0)的线段都和一条斜率大于(0)的一一对应。所以如果((i,j))不在坐标轴上我们还需要将总数乘上一个(2)

//minamoto
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,gcd[1005][1005];ll ans,t;
int GCD(int a,int b){
	if(gcd[a][b])return gcd[a][b];
	if(!a)return gcd[a][b]=b;
	if(!b)return gcd[a][b]=a;
	return gcd[a][b]=GCD(b,a%b);
}
void init(){
	for(int i=1;i<=m;++i)gcd[0][i]=i;
	for(int i=1;i<=n;++i)gcd[i][0]=i;
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)GCD(i,j);
}
int main(){
	scanf("%d%d",&n,&m),init();
	t=(n+1)*(m+1),ans=t*(t-1)*(t-2)/6;
	for(int i=0;i<=n;++i)for(int j=0;j<=m;++j)if(i||j){
		ans-=((!i||!j)?1ll:2ll)*(gcd[i][j]-1)*(n-i+1)*(m-j+1);
	}
	printf("%lld
",ans);return 0;
}