09_24

/*
 * Hàm phi Euler có một vài tính chất để giúp tính toán dễ hơn
 * 1. Tính chất 1:
 *   Nếu a và b nguyên tố cùng nhau thì: phi(ab) = phi(a) * phi(b)
 * 2. Tính chất 2:
 *   Nếu p là số nguyên tố: phi(p) = p - 1
 * 3. Tính chất 3:
 *   Nếu p là số nguyên tố: phi(p^a) = p^(a) - p^(a - 1)
 * 4. Tính chất 4:
 *   phi(1) = 0
 *
 * Từ các tính chất trên -> Hướng giải bài toán:
 *   Phân tích thành thừa số nguyên tố, đếm số mũ của số nguyên tố
 *   Ta có thể thấy tính chất 2 và 3 tương tự nhau, tính chất 2 là hệ quả của 3 với số mũ = 1
 *   Từ đó, dùng tính chất 3 để tính kết quả của hàm phi Euler
 */

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

#define MAX 10000
#define ll long long

// Những thứ cần chuẩn bị
ll expo(ll a, ll b);                  // Hàm tính số mũ
bool isPrime(ll n);                   // Hàm kiểm tra số nguyên tố

int main()
{
    ll n;
    scanf("%lld", &n);

    ll uoc[MAX];
    int so_mu[MAX];

    int index = 0;
    ll prime_number = 2;

    while (n > 1)
    {
        if ((n % prime_number == 0) && isPrime(prime_number))
        {
            uoc[index] = prime_number;
            so_mu[index] = 0;
            while (n % prime_number == 0)
            {
                n = n / prime_number;
                so_mu[index] += 1;
            }
            ++index;
        }
        ++prime_number;
    }

    ll answer = 1;

    for (int i = 0; i < index; ++i)
    {
        answer *= (expo(uoc[i], so_mu[i]) - expo(uoc[i], so_mu[i] - 1));
    }

    printf("%lld", answer);
}

// Hàm lũy thừa
ll expo(ll a, ll b)
{
    ll ans = 1;
    while (b > 0)
    {
        if (b & 1) ans = ans * a;
        a = a * a;
        b = b >> 1;
    }
    return ans;
}

// Hàm kiểm tra số nguyên tố
bool isPrime(ll n)
{
    if (n < 2) return false;

    for (ll i = 2; i <= sqrt(n); ++i)
        if (n % i == 0) return false;

    return true;
}