Submit solution
Points:
0.30 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Authors:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho ba số nguyên ~n~, ~m~, ~x~. Bạn cần đếm số lượng dãy ~a_1, a_2, \dots, a_n~ thoả:
Các phần tử ~a_i~ có giá trị thuộc ~[1, x]~.
Dãy thoả ~m~ điều kiện được biểu diễn bởi bộ ba phần tử ~(i, j, g)~ cho biết ~GCD(a_i, a_j) = g~.
Input
Dòng đầu tiên gồm ba số nguyên dương ~n~, ~m~, ~x~ (~3 \le n \le 9, 0 \le m \le n, 3 \le x \le 12~).
~m~ dòng tiếp theo, mỗi dòng gồm ba sốn nguyên dương ~i~, ~j~, ~g~ (~1 \le i, j \le n \; và \; i \ne j, 2 \le g \le x~).
Output
Một số nguyên duy nhất là số lượng dãy ~a_1, a_2, \dots, a_n~ thoả.
Scoring
~20\%~ test có ~n, m, x \le 7~.
~20\%~ test khác có ~|i - j| = 1~ với mọi truy vấn.
~60\%~ số test còn lại không có ràng buộc gì thêm.
Sample Input 1
2 1 5
1 2 3
Sample Output 1
1
Sample Input 2
3 2 6
1 2 3
3 1 2
Sample Output 2
2
Comments