Pre TS10 2023 #03 - Cặp số nguyên tố cùng nhau
Xem PDF
Nộp bài
Điểm:
1500 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
CPP.inp
Output:
CPP.out
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, NASM, Pascal, pypy3, Python, text
Cho một số nguyên dương n. Tìm số cặp số nguyên (x, y) mà 1 \le x \le n và 1 \le y \le n và gcd(x, y) = 1.
Input, Output và Subtasks
Input: (CPP.inp)
- Một dòng duy nhất gồm số nguyên dương n (1 \le n \le 2 \times 10^7).
Output: (CPP.out)
- Một dòng duy nhất là số lượng cặp số theo yêu cầu đề bài.
Subtasks
- Subtask 1 (25\%): n \le 2000.
- Subtask 2 (25\%): n \le 2 \times 10^5.
- Subtask 3 (25\%): n \le 2 \times 10^6.
- Subtask 4 (25\%): Không có giới hạn gì thêm.
Sample 1
Input (CPP.inp)
3
Output (CPP.out)
7
Note
- Tất cả các cặp số nguyên dương không vượt quá 3 đều nguyên tố cùng nhau, trừ các cặp (2, 2) và (3, 3).
Bình luận