题解 P2158 【[SDOI2008]仪仗队】
第一眼看到这题，哇塞似曾相识
仔细一想，这是P1447能量采集的缩小版和简化版
于是，我就用着过P1447的代码模板稍微改了一下
思路是这样的：
比如n = 5
-
. . . .
-
. . . .
-
. . . .
* . . . .
C * - - -
不难发现，标星号的两个点无论n是几都能看到，而且都看不到标减号的位置
那么问题就是剩下的标小点点的位置，也就是一个n-1边长的矩阵 ps：这里就和能量采集差不多了
为剩下的矩阵重新定义坐标，并标出能看到的：
4 o . o .
3 o o . o
2 o . o .
1 o o o o
c 1 2 3 4
若被标注点的坐标是(x,y)的话，很容易发现，如果gcd(x,y)=1，就满足
那就只用数数x,y<=n且gcd(x,y)=1的个数就好啦
怎么数呢？
首先假定所有的x,y都满足，然后开始筛
仍然很容易发现，gcd(x,y)=m(m<=n)的个数为(n/m)^2向下取整的结果
令q[i]为gcd(x,y)=i的个数，也就是说，我们要求的是q[1]
gcd(x,y)=4的（也就是等于n的，之后往下依次递减）有1个（也就是(n/4)*(n/4)个），则q[4]=1，但为了避免之后重复计算，要将4的因数的q值都减q[4]，即q[1]--,q[2]--
gcd(x,y)=3的有1个（也就是(n/3)*(n/3)）个，同样的，q[1]--
q[2]=(n/2)*(n/2)=4，但因为其中有一个被q[4]减去了，所以q[2]=3，同样q[1]-=3
那么，q[1]=(n/1)*(n/1)-q[4]-q[3]-q[2]=15，右上角的矩阵就处理完了
然后加上一开始扔掉的两个，15+2=17就是最终答案
时间复杂有点高，枚举一遍n，对于每个i都求一遍因数，那么时间复杂度就是n*sort(n)
#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
ll q[100100] = {0}; //q[i]表示gcd(x,y)=i的个数
int main(void)
{
ll n;
cin >> n; n--; //直接处理右上角的那个子矩阵，所以n--
for (ll i = n; i >= 1; i--)
q[i] = ((n / i) * (n / i)); //预处理q[i]，然后在下面筛去重复的
for (ll i = n; i >= 2; i--) {
for (ll j = 2; j*j <= i; j++) //寻找i的因数
if (!(i % j) && i != j) { //如果j是i的因数，则q[j]-=q[i]
q[j] -= q[i];
if (j != i/j) q[i/j] -= q[i]; //这个很好理解，比如i=10的时候只枚举1~3，所以在j=2的时候就要筛掉q[5]
}
q[1] -= q[i];
}
cout << q[1]+2; //最后加上2
return 0;
}另外附上P1447的代码：
#include <iostream>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
ll q[100100] = {0};
int main(void)
{
ll n, m;
cin >> n >> m;
ll minn = min(n, m);
ll ans = 0;
for (ll i = minn; i >= 1; i--)
q[i] = ((n / i) * (m / i));
for (ll i = minn; i >= 2; i--) {
for (ll j = 2; j*j <= i; j++)
if (!(i % j) && i != j) {
q[j] -= q[i];
if (j != i/j) q[i/j] -= q[i];
}
q[1] -= q[i];
}
for (ll i = 1; i <= minn; i++) ans += q[i]*i;
cout << ans*2-(ll)n*m;
return 0;
}