P2158 P1447 一蓝一紫

chenhaotian0219 · 2023-03-29 21:03:21 · 个人记录

这是我的第一篇博客！！！！！

今天我们来看一道蓝题 P2158

注意：下文的 / 皆指整数除法

>>作者主页<<

>>题目链接<<

[SDOI2008] 仪仗队

题目描述

作为体育委员，C 君负责这次运动会仪仗队的训练。仪仗队是由学生组成的 N \times N (1 \le N \le 40000)的方阵，为了保证队伍在行进中整齐划一，C 君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐（如下图）。

现在，C 君希望你告诉他队伍整齐时能看到的学生人数。

一、基础说明，求出公式

我们设左数第 a 列，后数第 b 列的同学，坐标为(a-1,b-1)

那么，C 君的坐标为 (0,0)

现在我们即对题目完成建模：在一个从 (0,0) 到 (n-1,n-1) 的点阵中，有多少点能被 (0,0) 点“看到”呢？

那么如何判定一个点是否看得到呢？

我们假设对于一个存在的点 (x,y)，那么，原点和该点连线方向往后的每一个点，都是看不到的。

即对任意整点 (x,y) ，点 ( \lambda x,\lambda y)( 1 < lambda) 是看不到的

也就是说，对于一个点 (x,y)，当 gcd(x,y) \neq 1 时这个点看不到

而对于任意满足 gcd(x,y)=1 的点 (x,y)，若它会被遮挡，则必定有整点 ({x\over m},{y\over m}),(m>1) 存在

根据 gcd(x,y)=1，我们能发现这样的点不存在

所以我们得出结论：一个点 (x,y) 能被看到，当且仅当 gcd(x,y)=1

我觉得我说的很清楚了吧！

还是不会的出门左拐去这里 >>绿色通道<<

好的，需要求的就是：

ans(1)=0

ans(n)= \sum_{x=1}^{n-1} \sum_{y=1}^{n-1} [gcd(x,y)=1]+2,n \geq 2

( +2 是因为 C 君还可以看到 (0,1) 和 (1,0) 的学生)

二、 gcd(x,y)=n 的 x,y 有多少？

n\geq2 $ 时我们要求 $ \sum_{x=1}^{n-1} \sum_{y=1}^{n-1} [gcd(x,y)=1]+2

那么我们设 g[k]= \sum_{x=1}^{n-1} \sum_{y=1}^{n-1} [gcd(x,y)=k]

这个比较难求，对吧？

我们可以求出 s=\sum_{x=1}^{n-1} \sum_{y=1}^{n-1} [x=ak,y=bk] (相当于 x,y 有公约数 k ，不一定是最大公约数)

易见 s=((n-1)/k)^2

其实 s 包括了 gcd(x,y)=k,2k,3k......((n-1)/k)k 的情况

那么，我们只需要倒着算 g[x]

递推公式为

g[x]=s-g[2x]-g[3x]-......-g[((n-1)/k)k]

那么答案正是

g[1]+2

三、食用代码区

不说话，直接上代码！

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,g[N];
int main(){
    cin >> n;
    if(n==1){
        cout << 0;
        return 0;
    }//特判
    for(int i=n-1;i>0;i--){
        g[i]=((n-1)/i)*((n-1)/i);
        // 这边我没有设s，直接把g[i]的初始值设成s了
        for(int j=i*2;j<n;j+=i)
            g[i]-=g[j];
    }
    cout << g[1]+2;
    return 0;
}