UCLN với N
Xem PDF
Điểm:
100 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn được cung cấp một số nguyên dương \(N\).
Nhiệm vụ của bạn là đếm số lượng số nguyên dương \(x(1 \le x \le N)\) sao cho \(gcd(x,N) = p\).
\(gcd(a,b)\) là ước chung lớn nhất của a và b.
Input
- Gồm hai số nguyên dương \(N\) và \(p\) \((p \le N)\).
Output
- Gồm một số nguyên duy nhất là kết quả của bài toán.
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(N \le 1000\).
- Subtask \(2\) (\(50\%\) số điểm): \(N \le 10^6\).
Example
Test 1
Input
6 2Output
2
Bình luận
Tác giả nên tăng thêm bộ nhớ dành cho Scratch vì Scratch khi làm xong bài nhưng tốn hơi nhiều bộ nhớ!
9 bình luận nữa