文章开始前先给大家安利我学长以前写的数论的blog：aliayc

互质

定义
$$\forall a,b\in N,若gcd(a,b)=1,则称a,b互质$$
​ 对于三个数或更多数的情况，gcd(a, b, c) = 1的情况称为a, b, c互质。把gcd(a, b) = gcd(a, c) = gcd(b, c) = 1称为a b c两两互质

欧拉函数

定义
$$\begin{gathered} 1\sim N中与N互质的数的个数称为欧拉函数，记为\phi (N) \\ 若在算数基本定理中，N=p_1^{a_1}{p}_2^{a_2}\dots p_m^{a_m}，则： \\ \varphi (N)=N\times \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\cdots \times \frac{p_m-1}{p_m}=N\ast \prod _{质数p|N}(1-\frac{1}{p}) \end{gathered}$$
证明：

​ 设p是N的质因子，1~N中p的倍数有1p，2p…(N / p) * p共 N / p个。同理设q是N的质因子，1~N中q的倍数N / q个。如果把这些数都去掉，即去掉了$\frac{N}{q}+\frac{N}{p}$个数，那么 p * q 的倍数被排除了两次，需要再加回来一次（容斥原理）。因此1~N中不与N含有共同因子 p 或 q 的数的个数为：
$$N-\frac{N}{q}-\frac{N}{p}+\frac{N}{pq}=N\ast (1-\frac{1}{p}-\frac{1}{q}+\frac{1}{pq})=N(1-\frac{1}{p})(1-\frac{1}{q})$$

质因数分解求欧拉函数

时间复杂度$O(\sqrt{N})$

 int phi(int x){
    int res = x;
    for(int i = 2; i <= x / i; i++){
        if(x % i == 0){
            res = res / i * (i - 1); // 先除防止爆int 
            while(x % i == 0) x /= i;
        }
    }
    if(x > 1) res = res / x * (x - 1);
    
    return res;
}

筛法求欧拉函数

$O(N)$时间求出1~N中所有的数的欧拉函数

• 当 i 为质数的时候，显然根据互质的定义显然 i 的欧拉函数是 i - 1

• 当i % prime[j] == 0 的时候$\phi (pj\ast i)$，说明pj是i的一个质因子。回顾欧拉函数的公式发现，对于质因子的次数来说是不影响欧拉函数的取值的。pj * i 与 i 相比，只是分解质因数的时候在 pj 那一项多了一个 pj 的次数，所以 pj * i 的所有质因子都在 i 中出现过了，所以相较于$\phi (i)$来说，就是$\phi (pj\ast i)=pj\ast \phi (i)$

• 当i % prime[j] != 0 的时候，那么 pj 就是 i * pj 的最小质因子，并且 pj 不是 i 的质因子，所以$\phi (pj\ast i)=pj\ast i\ast \frac{p_1-1}{p_1}\times \frac{p_2-1}{p_2}\cdots \times \frac{p_m-1}{p_m}\times \frac{pj-1}{pj}=pj\times \phi (i)\times \frac{pj-1}{pj}=\phi (i)\times (pj-1)$

void get_phi(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!vis[i]){
            prime[cnt_prime++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; prime[j] <= n / i; j++){
            vis[prime[j] * i] = 1;
            if(i % prime[j] == 0){
                phi[i * prime[j]] = prime[j] * phi[i];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

关于欧拉函数的应用，会在下一节关于同余的一节中的欧拉定理进行阐述

性质

1. $\forall n>1,1\sim n中与n互质的数的和为n\ast \phi (n)/2$
2. $若a,b互质，则\phi (ab)=\phi (a)\phi (b)$

证明：

1. 因为gcd(n, x) = gcd(n, n - x)，所以不互质的数 x, n - x成对出现，平均值为 n / 2。因此，与 n 互质的数的平均值也是 n / 2，所以总和就是$\frac{n}{2}\times \phi (n)$
2. 欧拉函数定义显然可得

积性函数

对于性质2来说我们推广到一般的函数来说

定义

$$如果a,b互质,有f(ab)=f(a)\ast f(b)，那么称函数f为积性函数$$

性质

3. 若 f 是积性函数，则$f(n)={\prod }_{i=1}^{m}f(p_i^{c_i})$（算数基本定理）
4. 若 p|n，且 $p^2|n$，则$\varphi (n)=\varphi (n/p)\ast p$
5. 若 p|n，且$p^2\nmid n$，则$\varphi (n)=\varphi (n/p)\ast (p-1)$
6. ${\sum }_{d|n}\varphi (d)=n$

证明：

3. 根据定义显然成立
4. 若 $p|n$且$p^2|n$，说明n和n/p包含相同的质因子p，只是p的指数不同。根据欧拉函数的定义，写出$\varphi (n)$和$\varphi (n/p)$，两者相除，商为 p ，得证
5. 若 $p|n$但$p^2\nmid n$，则p , n /p 互质，因为欧拉函数是积性函数，所以$\varphi (n)=\varphi (n/p)\ast \varphi (p)$，得证
6. 设$f(n)={\sum }_{d|n}\varphi (d)$。设两个互质的数n, m，则$f(nm)={\sum }_{d|nm}\varphi (d)$；因为欧拉函数是积性函数，故$f(nm)={\sum }_{d|nm}\varphi (d)=({\sum }_{d|m}\varphi (d))\ast ({\sum }_{d|n}\varphi (d))=f(n)\ast f(m)$。对于单个质因子，$f(p^m)={\sum }_{d|p^m}\varphi (d)=\varphi (1)+\varphi (p)+\cdots +\varphi (p^m)$是一个等比数列求和加上1，结果为$p^m$。所以$f(n)={\prod }_{i=1}^{m}f(p_i^{c_i})={\prod }_{i=1}^m{p}_i^{c_i}=n$

对于性质4和性质5来说，上面的线性筛求欧拉函数就是用的这两个性质

题目

洛谷P2158

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。
现在，C君希望你告诉他队伍整齐时能看到的学生人数。

题解可以去看洛谷很多大佬的分析，我这里就不放了qwq

// Problem: P2158 [SDOI2008]仪仗队
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2158
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Code by: ING__
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#define ll long long
#define re return
#define Endl "\n"
#define endl "\n"

using namespace std;

typedef pair<int, int> PII;

const int N = 4e4 + 10;

int n;
int cnt_prime;
int prime[N];
ll phi[N];
bool vis[N];

void get_phi(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!vis[i]){
            prime[cnt_prime++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; prime[j] <= n / i; j++){
            vis[prime[j] * i] = 1;
            if(i % prime[j] == 0){
                phi[i * prime[j]] = prime[j] * phi[i];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
}

int main(){
	cin >> n;
	
	if(n == 1){
		cout << 0;
		return 0;
	}
	
	get_phi(n);
	
	ll res = 0;
	for(int i = 2; i < n; i++) res += phi[i]; // 因为坐标下标是从0开始的，最大的坐标是5
	cout << res * 2 + 3;
}