Bedao Regular Contest 17 - Dãy số
Xem dạng PDF
Gửi bài giải
Điểm:
0,60 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Đếm số dãy ~a~ nguyên dương độ dài ~n~ thỏa mãn:
~1 \leq a_i \leq m~
~gcd(a_1, a_2, \dots, a_n) = k~.
Input
Dòng duy nhất nhập ~3~ số nguyên dương ~n, m, k (1 \leq n, m, k \leq 10^6)~.
Output
In ra số dãy ~a~ thỏa mãn điều kiện.
Vì đáp án có thể rất lớn, in ra số dãy modulo ~998244353~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20~ | ~n, m, k \le 100~ |
| 2 | ~80~ | Không ràng buộc gì thêm |
Sample Input 1
3 4 2
Sample Output 1
7
Notes
Có các dãy ~a~ sau thỏa ~gcd(a_1, a_2, a_3) = 2~:
~(2, 2, 2)~
~(4, 2, 2)~
~(2, 4, 2)~
~(2, 2, 4)~
~(4, 4, 2)~
~(4, 2, 4)~
~(2, 4, 4)~
Bình luận