Phi hàm Euler

View as PDF
Submit solution
Points: 0.15 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • -2
    dangminh  commented on Nov. 6, 2024, 5:50 p.m.

    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  commented on May 19, 2021, 3:52 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.