Euler
Đề bài
Mô tả
Cho hai số nguyên dương và . Hãy tính tổng giá trị hàm phi Euler của bội số đầu tiên của , tức là
Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho .
Hàm phi Euler của số nguyên dương là số lượng số nguyên thỏa mãn và , trong đó là ước chung lớn nhất của và .
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và ().
Dữ liệu ra
In ra một dòng chứa đáp án: tổng giá trị hàm phi Euler của bội số đầu tiên của , lấy phần dư khi chia cho .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 4 | 9 | . |
| 1 3 | 4 | . |
Bình luận