오일러 피 함수

오일러 피 함수는 $n$이하의 $n$과 서로소인 수의 개수를 구하는 함수로 다음과 같은 식을 가지고 있습니다.

$k$는 $n$의 소인수이다.
$\phi(n) = n(1-\displaystyle\frac{1}{k_1})(1-\displaystyle\frac{1}{k_2})(1-\displaystyle\frac{1}{k_3})\dotsb(1-\displaystyle\frac{1}{k_m})$

유도

예를 들어 24를 예로 들면, 24의 소인수는 2, 3입니다. 따라서 24 이하의 2, 3의 배수를 모두 제거한다면,

$24 - (24/2) - (24/3) = 4$

그러나 24이하의 24와 서로소인 수의 개수는 8개인데, 4개가 나온 이유는 중복을 제거하지 않았기 때문입니다. 따라서 2와 3의 최소공배수인 6의 배수를 모두 제거한다면,

$24 - (24/2) - (24/3) + (24/6) = 8$
$24(1-\displaystyle\frac{1}{2})(1-\displaystyle\frac{1}{3}) = 8$ <- 곱셈을 전개하면 위의 식과 같습니다.

코드(BOJ 13926)

import random
import math
import sys
import decimal

miller_rabin = [2, 7, 61]

def rand():
    return random.randint(1, 21)

def power(base, exponent, mod):
    res = 1

    base %= mod
    while exponent > 0:
        if exponent % 2 == 1:
            res = res * base % mod
        exponent = exponent // 2
        base = (base*base)%mod
    return res

def m_r(n, a): # 밀러-라빈 소수 판별법
    d = n - 1
    while d%2 == 0:
        d //= 2
    x = power(a, d, n)
    if x==1 or x==n-1:
        return True
    while d != n-1:
        x = power(x, 2, n)
        d*=2
        if x==1:
            return False
        if x==n-1:
            return True
    return False

def isPrime(n):
    if n in miller_rabin:
        return True

    if n==1 or n%2==0:
        return False

    for i in miller_rabin:
        if not m_r(n, i):
            return False

    return True

def rec(n, list): # 소인수분해 : 폴라드-로
    if n == 1:
        return
    while n % 2 == 0:
        list.append(2)
        n //= 2
    if isPrime(n):
        list.append(n)
        return
    g = n
    def f(i):
        return (c + (i*i)%n)%n
    while True:
        if g==n:
            a = b = rand() % (n-2) + 2
            c = rand() % 20 + 1
        a = f(a)
        b = f(f(b))
        g = math.gcd(abs(a-b), n)
        if g != 1:
            break
    if isPrime(g):
        list.append(g)
    rec(n // g, list)

input = sys.stdin.readline
n = int(input())
k = []

rec(n, k)
k = set(k)

cnt = n
for i in k: # 정확도를 위해 decimal 사용
    cnt*=decimal.Decimal('1') - decimal.Decimal('1') / decimal.Decimal(f'{i}')

print(int(cnt))