1.相關定義

互質：a與b的最大公約數為1

歐拉函數：在1~n中，與n互質的數的個數就是歐拉函數的值

eg：

n=1時，歐拉函數的值為1，因為1和1是互質的

n=2是，值為2，因為1和2都是互質的

積性函數：f(1）= 1且f(xy) = f(x)f(y)，其中x與y互質

2.歐拉函數

性質：
1.若p為質數，則：φ(p) = p-1

解析：

因為p是質數，所以在1~p中與p有除了1以外的公約數的只有p本身，總共的數的個數為p，所以與p互質的數就是p-1個，即φ(p) = p-1
2.若p為質數，則：φ(p^k) = (p-1)p^(k-1)

解析：
對p^k進行分解質因數：p^k = p*p*p*p...*p（共k個）

我們發現p^k只有p本身，而p是質數，不能由其他數組合而成，所以p^k只能與p的倍數有除了1以外的公約數，而我們以每一個倍數的p為一個周期看待，每個周期內有p-1個與p^k

互質的數

3.歐拉函數屬于積性函數

即φ(xy) = φ(x)φ(y)

3.試除法求單個數歐拉函數?

公式解釋：單個數n的歐拉函數就是n乘上(pi-1)/pi的連乘

公式推導：

1.對n分解質因數

2.由于歐拉函數是積性函數，所以我們可以直接拆分開

3.由于pi是質數，根據歐拉函數的性質（若p為質數，則：φ(p^k) = (p-1)p^(k-1)），得到結果式子

4.我們將pi^(αi-1)中的pi^(-1)分離出去給到(pi-1)，于是就得到了(pi-1)/pi

5.根據pi的連乘是n分解質因數的得到的，所以pi的連乘換成n，得證

代碼實現：
?

int phi(int n)
{int answer = n;for (int i = 2; i <= n / i; i++){if (n % i == 0){answer = answer / i * (i - 1);//先除后乘防止溢出while (n % i == 0) n /= i;}}if (n > 1) answer = answer / n * (n - 1);return answer;
}

4.歐拉篩打表歐拉函數

我們可以在進行線性篩的時候順便計算記錄下對應數據的歐拉函數

線性篩代碼如下：
?

typedef long long ll;
const int N = 1e9;
bool f[N];
int a[N];
int count;
void get_prime(int n)
{for(ll i = 2; i <= n; i++){
//沒有被標記為true，說明是質數if(f[i] == false) {a[++count] = i;}
//進行線性篩for(int j = 1; i*a[j] <= n; j++){f[i*a[j]] = true;if(i % a[j] == 0) break;{          }
}

若數據是質數：根據歐拉函數的性質，歐拉函數的值就是該數-1

若數據不是質數：

（1）i%a[j] != 0：且a[j]是質數，所以i與a[j]互質，此時根據歐拉函數的性質

（φ(xy) = φ(x)φ(y)）可知，φ(x) = φ(i）*φ(a[j])

（2）i%a[j] == 0: φ(x) = φ(i)*a[j]

證明如下：

打表代碼：
?

typedef long long ll;
const int N = 1e9;
bool f[N];
int a[N];
int count;
int phi[N];
void get_prime(int n)
{phi[1] = 1;for(ll i = 2; i <= n; i++){
//沒有被標記為true，說明是質數if(f[i] == false) {a[++count] = i;phi[i] = i - 1;}
//進行線性篩for(int j = 1; i*a[j] <= n; j++){int x = i * a[j];f[i*a[j]] = true;if(i % a[j] == 0) {phi[x] = a[j] * phi[i];break;}else{phi[x] = phi[i] * (p[j]-1);}}          }
}

5.例題講解

?

審題：

本題需要我們找到從坐標原點出發可以直接看到的坐標個數

思路：
方法一：分析+歐拉函數

我們建立坐標徐后可以清楚發現，只要點在同一條從原點出發的直線路徑上，就只有第一個點可以被直接看到，其他的點都會被遮住。

而被遮住的點可以通過除以橫縱坐標的最大公約數變成第一個可以被看見的點，由于這個特性，我們發現最大公約數不為1的橫縱坐標的點都會被遮住（因為他們都可以轉換成直線上第一個被看見的點）

故可以被看見的點就是橫縱坐標互質的點，接下來我們分析如何求

首先我們分析第五列的點（先不看在坐標軸上的點），我們發現橫縱坐標互質的點的個數（可以被看到的數）其實就是當前橫坐標的歐拉函數。

故我們可以直接將1~n-1的數的歐拉函數累加起來，然后就得到了下半邊的可看到點位數，再根據對稱輪換，我們對結果乘2可以得到上下兩邊的可看到點數。但是此時我們的（1,1）被計算了兩次（要減1），而坐標軸上的（1,0）和（0,1）兩點還沒加上（要加2），綜合起來我們就要在當前結果的基礎上加一.

解題：

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 4e4 + 10;
int n;
//線性篩所需變量
bool st[N];
ll p[N],cnt;
ll phi[N];//歐拉函數
void get_phi()
{phi[1] = 1;for (ll i = 2; i <= n; i++){if (!st[i]){p[++cnt] = i;phi[i] = i - 1;}for (ll j = 1; i * p[j] <= n; j++){st[i * p[j]] = true;ll x = i * p[j];if (i % p[j] == 0){phi[x] = phi[i] * p[j];break;}else//i 與p[j]互質{phi[x] = phi[i] * (p[j] - 1);}}}
}
int main()
{cin >> n;get_phi();ll sum = 0;for (int i = 1; i < n; i++){sum += phi[i];}if (n == 1) cout << 0 << endl;elsecout << sum * 2 + 1 << endl;return 0;
}

其中計算歐拉函數就是使用線性篩來完成。

注意：累加的時候不要加到i==n的情況，因為我們的坐標是從0開始的，所以訪問到i==n其實就是越界訪問

P2158 [SDOI2008] 儀仗隊 - 洛谷