Cặp số nguyên tố cùng nhau (HSG9 NA 2023)

Điểm: 900 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 1G

Input: NTCN.inp

Output: NTCN.out

Tác giả:

Sunlight

Dạng bài

Tuấn là một học sinh rất yêu thích Tin học. Ước mơ của cậu sau này là trở thành một lập trình viên tài năng. Tuấn thường xuyên tìm hiểu các thông tin, sự kiện liên quan đến Công nghệ. Một sự kiện công nghệ nổi tiếng trên toàn thế giới trong thời gian gần đây là sự ra mắt robot thông minh ChatGPT của công ty công nghệ OpenAI. Tuấn cũng rất tò mò về ChatGPT nên đã sử dụng để giải bài toán. Bài toán mà Tuấn đưa cho ChatGPT như sau:

Cho số nguyên dương $n$ . Tìm số lượng các số nguyên dương $x$ nhỏ hơn $n$ thỏa mãn: $x$ và $n$ là hai số nguyên tố cùng nhau (tức là ước chung lớn nhất của $x$ và $n$ bằng $1$ ).

Thật là thú vị, khi Tuấn nhập $n=5$ . ChatGPT đưa ra kết quả là: Có $4$ số, cụ thể là các số: $1,2,3,4$ . Tuấn muốn các bạn lập trình giải bài toán này để cùng kiểm tra kết quả của ChatGPT nhé.

Input, Output và Subtasks

Input: (NTCN.inp)

Gồm một số nguyên dương $n$ ( $2\leq n\leq 10^9$ ).

Output: (NTCN.out)

Gồm một số nguyên duy nhất là số lượng số nguyên dương $x$ , nhỏ hơn $n$ và nguyên tố cùng nhau với $n$ .

Subtasks

Có $50\%$ số test ứng với $50\%$ số điểm thỏa mãn $2\leq n\leq 2000$ .
Có $40\%$ số test ứng với $40\%$ số điểm thỏa mãn $2000<n\leq 2\times 10^6$ .
Có $10\%$ số test ứng với $10\%$ số điểm thỏa mãn $2\times 10^6<n\leq 2\times 10^9$ .

Sample

Input (NTCN.inp)

Output (NTCN.out)

Notes

$n=5$ , trong $4$ số $1,2,3,4$ nhỏ hơn $n$ . Có $4$ số thỏa mãn: $x=1,2,3,4$ là các số nguyên tố cùng nhau với $n$ .

Sample

Input (NTCN.inp)

Output (NTCN.out)

Notes

$n=10$ , trong $9$ số $1,2,3,4,5,6,7,8,9$ nhỏ hơn $n$ . Có $4$ số thỏa mãn: $x=1,3,7,9$ là các số nguyên tố cùng nhau với $n$ .

Bình luận

Không có bình luận nào.