洛谷 P2158 [SDOI2008]仪仗队

洛谷 P2158 [SDOI2008]仪仗队

思路

斜率+求欧拉函数

将左下角第一个点看做((0,0))，由于正方形关于对角线对称，所以只考虑由对角线分割开来的一侧的三角，最后再乘以二即可，然后如果作图我们就可以发现，同在一条直线上的点只能看见一个，也就是说同在一条直线上的点会被这条直线上第一个点所遮挡，所以如果被遮挡的话他们所在直线的斜率一定相等（画图看一下同一条直线上点的斜率即可），假如一条直线上的某一个点是((x,y))，那这条直线的斜率就是(k = frac{y}{x})，这样我们就可以知道这条直线上的第一个点，假设这个点是((x_0,y_0))，那么(gcd(x_0,y_0)=1)，这条直线上后面的点((x_0 * n,y_0 * n))都会被这个点所遮挡，所以问题就可以转化为求

[sumlimits_{i = 2}^{n - 1}sumlimits_{j = 1}^{i}gcd(i,j) = 1 ]

显然后面的(sumlimits_{j = 1}^{i}gcd(i,j) = 1)就是求(i)的欧拉函数(phi(i))，所以最后我们要求

[ans = sumlimits_{i = 2}^{n - 1}phi(i) ]

因为我们只求了一个三角形，所以要(*2)，但是这还不够，因为((0,1),(1,0),(1,1))并没有算进去，所以还要(+3)，所以最后的答案就是(ans * 2 + 3)，注意特判一下(n=1)的情况，这种情况下是(0)。

代码

/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int read() {
	char c = getchar(); int x = 0, f = 1;
	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return x * f;
}

int n, cnt, maxn, phi[A], c[A], sum[A], p[A];
bool vis[A];

inline void getphi() {
	phi[1] = 1;
	for (int i = 2; i <= maxn + 1; i++) {
		if (!vis[i]) phi[i] = i - 1, p[++cnt] = i;
		for (int j = 1; j <= cnt && i * p[j] <= maxn + 1; j++) {
			vis[i * p[j]] = 1;
			if (i % p[j] == 0)  phi[i * p[j]] = phi[i] * p[j];
			else phi[i * p[j]] = phi[i] * (p[j] - 1);
		}
	}
	sum[2] = phi[2];
	for (int i = 3; i <= maxn + 1; i++) sum[i] = sum[i - 1] + phi[i];
}

signed main() {
	maxn = n = read();
	getphi();
	if (n == 1) return puts("0"), 0;
	cout << sum[n - 1] * 2 + 3 << '
';
	return 0;
}