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.