phifunction.cpp

Bài toán

Tính phi hàm Euler của số n.

phi(1) = 1

phi(n) = số lượng số nhỏ hơn hoặc bằng n mà là nguyên tố cùng nhau với n.

Độ phức tạp

phi(n) : chưa xác định (khoảng sqrt(n))

Code này của : Nguyễn Tiến Trung Kiên

#include <stdio.h>

#define long long long

long Power[230997][15];  // positive

long power(int a, int k) {

    if (k == 0) return 1;

    if (Power[a][k] > 0) return Power[a][k];

    long p = power(a, k / 2);

    if (k & 1)

        return Power[a][k] = p * p * a;

    else

        return Power[a][k] = p * p;

}

long phi(int p, int k) {

    // phi of p^k with p is a prime

    if (k == 0) return 1;

    return (p - 1) * power(p, k - 1);

}

long Phi[230997];  // positive

long phi(int m) {

    int om = m;

    long r = 1;

    if (Phi[om] > 0) return Phi[om];

    for (int i = 2; i * i <= m; i++) {

        int k = 0;

        while (m % i == 0) {

            k++;

            m /= i;

        }

        r *= phi(i, k);

    }

    if (m > 1) r *= phi(m, 1);

    return Phi[om] = r;

}

int n;

int main() {

    for (;;) {

        scanf("%d", &n);

        if (n == 0) return 0;

        long r = phi(n);

        printf("%lld\n", r);

    }

}

Nhận xét

phi(n) luôn không vượt quá n. Đặt kiểu khai báo long long như trên kia là không cần thiết. Xin lỗi các bạn vì sự bất tiện này.