Totient Function
(Integer/Totient.py)

View this file on GitHub
Last update: 2023-03-18 02:55:12+09:00

Outline

Euler の Totient 関数 $\varphi$ に関する計算を行う.

正の整数 $N$ に対して, $N$ と互いに素な $1$ 以上 $N$ 未満の整数の個数を $\varphi(N)$ と書く.

Theory

Euler の Totient 関数に対して, 以下の性質が成り立つ.

素数 $p$ と非負整数 $k$ に対して, $\varphi(p^k) = p^k - p^{k-1} = p^{k-1} (p-1)$.
互いに素な正の整数 $m, n$ に対して, $\varphi(mn) = \varphi(m) \varphi(n)$.

このことから, $N$ の素因数分解を

\[N = p_1^{e_1} \times \dots \times p_r^{e_r} = \prod_{i = 1}^r p_i^{e_i} \quad (i \neq j \Rightarrow p_i \neq p_j)\]

としたとき,

\[\varphi(N) = \prod_{i=1}^r p_i^{e_i-1} (p_i - 1) = N \prod_{i=1}^r \left(1 - \dfrac{1}{p_i} \right)\]

となる.

$N$ の素因数分解は試し割りを用いると, $O(\sqrt{N})$ 時間, 高速な方法で $O(N^{1/4})$ 時間で求められるので, $\varphi(N)$ もこれらと同程度の時間で求められる.

$\varphi$ の性質

$\varphi$ について, 以下が成り立つ.

$N \geq 2$ とする. $\mathbb{Z}/N \mathbb{Z}$ における可逆元の個数は $\varphi(N)$ 個である.
$d$ を $N$ の約数とする. $\gcd(N,x) = \frac{N}{d}$ となる $N$ 未満の非負整数の数は $\varphi(d)$ 個である. このことから, $\displaystyle \sum_{d \mid N} \varphi(d) = N$ が成り立つ.

Code

#Euler's Totient関数
def Euler_Totient(N, mode=True):
    """ 1 以上 N 以下の整数のうち, N と互いに素な整数の個数 phi (N) を求める.

    Args:
        N (int): 正の整数
        mode: False にすると, N "以下" が N "未満" になる (phi(1) が True だと 1, False だと 0 になるだけの違いである) 

    Returns:
        int: varphi (N)
    """

    assert N>=0,"Nが非負整数ではない."

    if N==1:
        return 1 if mode else 0

    e=(N&(-N)).bit_length()-1
    if e>0:
        phi=1<<(e-1)
        N>>=e
    else:
        phi=1

    e=0
    while N%3==0:
        e+=1
        N//=3

    if e>0:
        phi*=pow(3,e-1)*2

    flag=0
    p=5
    while p*p<=N:
        if N%p==0:
            e=0
            while N%p==0:
                e+=1
                N//=p

            phi*=pow(p,e-1)*(p-1)

        p+=2
        flag^=1

    if N>1:
        phi*=N-1

    return phi

#Euler's Totient関数
def Euler_Totient_List(N, mode=True):
    """k=0,1,...,N に対して, 1以上k以下の整数のうち, kと互いに素な整数の個数 φ(k) を求める.

    N:正の整数
    mode: False にすると, N "以下" が N "未満" になる (phi(1) が True だと 1, False だと 0 になるだけの違いである) 
    """

    assert N>=0,"Nが非負整数ではない."

    phi=list(range(N+1))
    for p in range(2,N+1):
        if phi[p]==p:
            for j in range(p,N+1,p):
                phi[j]=phi[j]//p*(p-1)

    if not mode and N>=1:
        phi[1]=0

    return phi

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Totient Function (Integer/Totient.py)

Outline

Theory

$\varphi$ の性質

Code

Totient Function
(Integer/Totient.py)