Phi hàm Euler

Xem dạng PDF
Gửi bài giải
Điểm: 0,15 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong số học, hàm Euler ~\varphi~ của một số nguyên dương ~n~ được định nghĩa là số lượng các số nguyên dương nhỏ hơn hoặc bằng ~n~ và nguyên tố cùng nhau với ~n~.

Cho số nguyên dương ~n~ ~\left(1 \le n \le 10^6\right)~. Tính giá trị của hàm Euler ~\varphi~.

Input

Dòng đầu chứa số nguyên ~T~ là số test ~\left(T \le 20000\right)~.

~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~n~.

Output

~T~ dòng, mỗi dòng ghi kết quả của test tương ứng.

Sample Input

5
1
2
3
4
5

Sample Output

1
1
2
2
4

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 2
    dangminh  đã bình luận lúc 6, Tháng 11, 2024, 17:50

    Hint giải bài này ạ :V

    tính phi theo kiểu sàng (tương tự sàng nguyên tố)

    sử dụng công thức:

    • Nếu i là số nguyên tố -> nó có n-1 số nguyên tố cùng nó.

    • Nếu i ko phải là số nguyên tố

    => i là hợp số

    <=> i có thể phân tích thành tích các thừa số nguyên tố dạng p1^q1 với p1 là số nguyên tố q1 là số mũ thỏa mãn.

    => phi(i) = i x (1-1/p1) x (1-1/p2) x .. x(1-1/pm)

    vậy nếu i là số nguyên tố thì phi(i)=i

    nên Ta có thể tính phi j từ các i nguyên tố đã tính trước.

    <=> phi[j] *= (1-1/i) với i là các số nguyên tố.

    Code sàng tham khảo:

    fu(i,1,maxn) phi[i] = i;

    fu(i,2,x) if(phi[i]==i) for(int j=i; j<=x; j+=i) phi[j]*=(1-1/i);


  • -34
    MrMinhFly  đã bình luận lúc 19, Tháng 5, 2021, 3:52

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.