オイラーのφ関数と競プロにおける例題 - プログラミング初心者の勉強日記

競技プログラミングでオイラーのφ関数を用いる問題を見つけたので、本記事では、オイラーのφ関数について軽く説明した後に、どのように用いたかの例を挙げます.

オイラーのφ関数
オイラーのφ関数の性質
オイラーのφ関数を用いる問題
- エラトステネスの篩の考え方を用いたオイラーのφ関数の求め方
- 例題の解答例

オイラーのφ関数

自然数 $n$ に対して、 $n$ と互いに素である $n$ 以下の自然数の個数を $\phi(n)$ で与えるとき、 $\phi(n)$ はオイラーの $\phi$ 関数 (ファイ関数) と呼ばれます. (オイラーのトーシェント関数とも呼ばれる.)

例えば、3と互いに素である3以下の自然数は、1と2の2つなので、 $\phi(3) = 2$ となります.

オイラーのφ関数の性質

$p$ が素数であるとき $$ \phi(p) = p - 1 $$ が成り立ちます. これは、 $1 \leq x \leq p - 1$ である $x$ に対して、 $p$ が素数なので、 $gcd(x, p) \neq 1$ となる $x$ が存在しないことから容易に確認できます. ここで、 $gcd(x, p)$ は $x$ と $p$ の最大公約数を表します.
自然数 $k$ に対して、 $1 \leq x \leq p^{k}$ である $x$ の中に $p$ の倍数であるものは $p^{k - 1}$ 個存在するので、 $p$ の倍数である個数を引いてあげらば良いことから、 $$ \phi(p^{k}) = p^{k} - p^{k - 1} = p^{k - 1}(p - 1) = p^{k}(1 - \frac{1}{p}) $$ が成り立ちます. ( $p^{1}, p^{2}, \cdots p^{k - 1}$ の $k - 1$ 個)
$gcd(m, n) = 1$ である自然数 $m, n$ に対して、 $$ \phi(mn) = \phi(m)\phi(n) $$ が成り立ちます.

オイラーのφ関数を用いる問題

オイラーのφ関数を用いる問題としてAOJのFarey Sequenceという問題がありました.

そもそもFarey Sequenceとはファレイ数列というもので初等整数論における興味深い性質をもつそうです. (この問題を解くまでファレイ数列の存在を知りませんでした...)

ファレイ数列とは、既約分数を順に並べた一群の数列であるとWikipediaに書いてありました.

もう少し具体的に言うと、一般項を $F_n$ としたとき、 $F_n$ とは、 $n$ 以下の分母を持つ0以上1以下の全ての既約分数を小さな順から並べたものだそうです.

例えば $$ F_3 = (\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}) $$ となりますし、 $$ F_4 = (\frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}) $$ となります.

AOJの問題では、 $n$ が与えられたときの $F_n$ の個数を求めるという問題です.

上で挙げた、 $F_3$ と $F_4$ に着目すると、 $F_4$ は $F_3$ に $\frac{1}{4}$ と $\frac{3}{4}$ が加わっていることがわかります.

つまり、4以下の自然数のうち、4と互いに素な自然数の個数分だけ追加されています. これはオイラーのφ関数を用いて定式化することができ、

$$ F_4 = F_3 + \phi(4) $$ と表現できます. つまり一般的に、

$$ F_n = F_{n - 1} + \phi(n) $$

が成立します. あとは、オイラーのφ関数を全ての自然数に対してあらかじめ求めておくことで、AOJの問題を解くことができます.

しかし今回の問題では、愚直にオイラーのφ関数を全ての自然数に対して求めていては、その自然数を素因数分解する必要があるので間に合いません.　そこでエラトステネスの篩の考え方を用いて求めることを考えます. (エラトステネスの篩の考え方は非常に単純なのでWikipediaを参照してください.)

エラトステネスの篩の考え方を用いたオイラーのφ関数の求め方

さて、 $1 \leq n \leq N$ である全ての $n$ に対して $\phi(n)$ を求めます.

まず、 $n = \prod_{k = 1}^{K} p_k^{e_k}$ で表したとき、

$$ \phi(n) = n \prod_{k = 1}^{K}(1 - \frac{1}{p_k}) $$ が成り立ちます.

したがって、 $n$ に対して、全ての素因数について $1 - \frac{1}{p} = \frac{p - 1}{p}$ をかけていけば良いことになります.

アルゴリズム的には以下のようになります.

phi[N + 1]を用意し、phi[i] = iと初期化する.
phi[i] = iのときN以下の全てのiの倍数に対して $\frac{i - 1}{i}$ をかける.
2の処理を2からNまで繰り返す.

2の処理で全ての因子に対して $\frac{p - 1}{p}$ をかけ合わせるという処理を実現しています. これをプログラムで表現すると以下のようになります.

for(int i = 0; i <= N ; i++) phi[i] = i;
for(int i = 2; i <= N; i++) {
    for(int j = i; j <= N; j += i) phi[j] = phi[j] / i * (i - 1);
}

これで計算量を抑えながらオイラーのφ関数の準備が整いました. あとは、 $F_n = F_{n - 1} + \phi(n)$ の処理を書いて出力すれば終わりです.

なお初期条件は $F_0 = 1, F_1 = 2$ です.

例題の解答例

以下に全体プログラムを載せておきます.

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

ll MAX = 1000000;
ll dp[1000001];
ll phi[1000001];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    rep(i, 0, MAX + 1) phi[i] = i;
    rep(i, 2, MAX + 1) {
        if(phi[i] == i) {
            for(int j = i; j <= MAX; j += i) {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }

    dp[0] = 1;
    dp[1] = 2;
    rep(i, 2, MAX + 1) dp[i] = dp[i - 1] + phi[i];

    int t;
    cin >> t;
    rep(i, 0, t) {
        int n;
        cin >> n;
        cout << dp[n] << endl;
    }
}