EGCD - Cặp ước chung lớn nhất
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.099s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho 2 số ~a~ và ~m~ . Hãy đếm xem có bao nhiêu số nguyên dương ~k~ thỏa mãn ~ 0 \le k < m ~ . Mà ~ \gcd(a+k,m) = \gcd(a,m) ~ .
Chú ý: ~ \gcd(a,b) ~ là ước chung lớn nhất của 2 số a,b.
Input
Gồm 1 dòng chứa 2 số nguyên dương ~ a,m ~ (~ 1\le a < m \le 10^{10} ~ ).
Output
In ra kết quả bài toán
Sample
Input #1
3 5
Output #1
4
Hint
Trong ví dụ trên có tất cả 4 số là : 0,1,3,4
Bình luận