题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4483

题目大意

在n*n的网格内找到3个格点,使它能构成三角形,问能构成多少个三角形?

这题我写了很久,总是出现各种小错误,最后还是屈服看了别人的题解,发现了long long的大坑。

题解

总共有t=(n+1)*(n+1)个格点,所以令n++。

1。任取三个点ans=c(t,3)

2。去掉在一条直线三的三个点ans=ans-c(n,3)*n*2

3。还要去掉在一条斜线上的三个点:

对于长宽为i,j的矩形,对角线上有gcd(i,j)-1个格点(不包括两端点),这样我们就能枚举矩形,去掉不能构成三角形的三个点则要去掉的方案数为∑∑(n-i)*(n-j)*(gcd(i,j)-1);

本题n太大,还要优化成O(n)复杂度才可以:令i=a*k,j=b*k,其中k为(i,j)的最大公约数则条件3的方案数。

sum

=∑∑∑(n-a*k)*(n-b*k)*(k-1)

=∑∑∑(n*n-(a+b)*n*k+a*b*k*k)*(k-1)

=∑[k](k-1)*(n*n*∑∑1+n*k*∑∑(a*b)+k*k*∑∑(a*b))

其中i,j<n,所以a,b<=(n-1)/k=m;

phi[i]为欧拉函数,a,b<=m中,∑∑=a,b两两互质的个数=1+(phi[2]+phi[3]+...+phi[m])*2

phi[i]的个数只是说a<b,b=i时有多少个,还有a>b,所以要乘以2,除了a=b=1以外

定理

如果gcd(a,b)==1,则gcd(a,a-b)==1。

所以phi[i]个与i互质的数种,成对出现,每对之和为i所以∑∑(a+b)=∑(phi[i]/2*i+phi[i])*2

由上述定理可以知道:phi[i]个互质的数与i的乘积之和为i*(x1+x2+...+xm)=i*ph[i]/2*i;

所以∑∑(a*b)=∑(phi[i]*i*i/2)*2

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100000;
const long long MOD = 1000000007;
long long a[N + 5], b[N + 5], c[N + 5], phi[N + 5];

void init() {
	memset(phi, 0, sizeof(phi));
	phi[1] = 1;
	for (int i = 2; i <= N; ++i)
		if (!phi[i])
			for (int j = i; j <= N; j += i) {
				if (!phi[j]) phi[j] = j;
				phi[j] = phi[j]/i*(i - 1);
			}
	a[1] = 1, b[1] = 2, c[1] = 1;
	for (int i = 2; i <= N; ++i) {
		a[i] = (a[i - 1] + phi[i]*2) % MOD;
		b[i] = (b[i - 1] + phi[i]*i*3) % MOD;
		c[i] = (c[i - 1] + (phi[i]*i % MOD)*i) % MOD;
	}
	return;
}

int main() {
	init();
	int t;
	scanf("%d", &t);
	while (t--) {
		long long n;
		scanf("%I64d", &n);
		++n;
		long long nn = n*n % MOD;
		long long ans = ((nn*(nn - 1) % (MOD*6))*(nn - 2) % (MOD*6))/6;
		ans -= ((nn*(n - 1) % (MOD*6))*(n - 2)*2 % (MOD*6))/6;
		long long sum = 0;
		for (long long i = 2; i < n; ++i) {
			long long x = (n - 1)/i;
			sum = (sum + (i - 1)*(((a[x]*n % MOD)*n % MOD) - ((n*i % MOD)*b[x] % MOD) + ((i*i % MOD)*c[x] % MOD))) % MOD;
		}
		ans = ((ans - sum*2) % MOD + MOD) % MOD;
		printf("%I64d\n", ans);
	}
	return 0;
}
转载保留版权:http://haipz.com/blog/i/5949 - 海胖博客