Submit solution
Points:
0.60 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
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)~
Comments