Euler's totient function

romophic-library1 min read (20 min read total)

インデックス変換(2D,3D)1 min read

累積和(1D,2D,3D)1 min read

LazySegmentTree1 min read

Euler's totient function1 min read

SegmentTree1 min read

UnionFind1 min read

WeightedUnionFind1 min read

進数変換1 min read

chmax/chmin1 min read

二分探索1 min read

入出力高速化1 min read

約数列挙1 min read

素因数分解1 min read

繰り返し二乗法1 min read

BellmanFord1 min read

BigInt2 min read

Dijkstra1 min read

DirectedGraph1 min read

Kruskal1 min read

Mo's Algorithm1 min read

RollingHash1 min read

強連結成分分解(SCC)1 min read

SuffixArray1 min read

TopologicalSort1 min read

UndirectedGraph1 min read

WarshallFloyd1 min read

getFarthestVertex(最遠頂点を求める)1 min read

getGraphDiameter(木の直径を求める)1 min read

文字列のith以降で文字cが出現する最小のindex1 min read

SimulatedAnnealing1 min read

ModInt1 min read

Overview

用途
計算量
使い方
実装

Euler's totient function

July 29, 2024

1 min read

用途

オイラーのトーシェント関数. $n \in \mathbb{N}$ に対して, $n$ と互いに素である $1$ 以上 $n$ 以下の自然数の個数 $φ(n)$ を与える.
nの素因数分解が

n = \prod_{k=1}^{d}p_k^{e_k}

と表されるとき,

\phi (n) = \prod_{k=1}^{d}\left(p_k^{e_k} - p_k^{e_k-1}\right) = n\prod_{k=1}^{d}\left(1-\frac{1}{p_k}\right)

と変形できることを利用して計算する。

計算量

$O(\sqrt{n})$

使い方

1
int res = euler_phi(n);

実装

1
int euler_phi(int n) {
2
  int ret = n;
3
  for (int i = 2; i * i <= n; i++) {
4
    if (n % i == 0) {
5
      ret -= ret / i;
6
      do
7
        n /= i;
8
      while (n % i == 0);
9
    }
10
  }
11
  return n > 1 ? ret - ret / n : ret;
12
}

Update available

New content is available, click on reload button to update.

Downloading for offline use...