Tính hàm phi Euler

Tác giả:

Dạng bài

Điểm: 300 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong số học, Hàm Euler \(\phi\) 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\).

Yêu cầu: Cho số nguyên dương \(n\). Tính giá trị của \(\phi(n)\).

Input

Dòng thứ nhất chứa số \(t(1 \le t \le 50)\) - Thể hiện số lượng testcase.
t dòng tiếp theo, mỗi dòng chứa một số nguyên \(n(1 \le n \le 10^8)\).

Output

Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

Test 1

Input

Output

Bình luận

Code uy tính 100 phần trăm nhé!

def euler_totient(n):  
    result = n  
    p = 2  
    while p * p <= n:  
        if n % p == 0:  
            while n % p == 0:  
                n //= p  
            result -= result // p  
        p += 1  
    if n > 1:  # nếu n còn lại là một số nguyên tố lớn hơn 1  
        result -= result // n  
    return result  

def main():  
    import sys  
    input = sys.stdin.read  
    data = input().split()  

    t = int(data[0])  
    results = []  

    for i in range(1, t + 1):  
        n = int(data[i])  
        results.append(euler_totient(n))  

    for res in results:  
        print(res)  

if __name__ == "__main__":  
    main()

-4

penistone 6:42 p.m. 18 Tháng 2, 2024 ← đã chỉnh sửa →

Gợi ý

ϕ(\(n\))=\(n\) * (1-1/\(p_1\)) * (1-1/\(p_2\)) * ... * (1-1/\(p_m\)) với \(p\) là các ước nguyên tố riêng biệt của \(n\)

Code

C++: https://ideone.com/WYeCpN

1 phản hồi

4

dang7rickroll 3:56 p.m. 29 Tháng 11, 2021 ← chỉnh sửa 2 →

Suggest bản khó hơn với \(N \le 10^{12}\)

1 phản hồi

2

new4letuantu 3:49 p.m. 29 Tháng 11, 2021

bài này cày trâu cx ac mà nên 300 là hơi cao :v

-8

nguyendanghau2006 4:06 p.m. 27 Tháng 11, 2021

bài ni tui nghĩ 200p đủ r, ko tới 300 đâu .-.

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.