6543: Travel plan
内存限制：256 MB
时间限制：1.500 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
Bob lives on a magical land. There are n cities and m roads on the land. The length of the i-th road is wi, and the length is an integer between 1 and L. Each road connects two cities. The land can be viewed as a graph of n points and m edges.
This land is magical because Bob was surprised to find that there are no simple circuits with an even total length in this land!
Bob likes to travel. If Bob takes a simple path from x to y (x<y), the happiness value is the greatest common factor (gcd) of the lengths of all roads on the path.
simple path:A path is called a simple path if the vertices on the path do not repeat each other.
simple circuit:A circuit in which the vertices are not repeated except for the first and last vertices is called a simple circuit
Bob wants to count all possible travel paths.
Define F(k) as the total number of travel paths with happiness value k, modulo 998244353.
Please find F(1)⨁F(2)⨁F(3)⨁...⨁F(L),where ⨁ represents XOR.
This land is magical because Bob was surprised to find that there are no simple circuits with an even total length in this land!
Bob likes to travel. If Bob takes a simple path from x to y (x<y), the happiness value is the greatest common factor (gcd) of the lengths of all roads on the path.
simple path:A path is called a simple path if the vertices on the path do not repeat each other.
simple circuit:A circuit in which the vertices are not repeated except for the first and last vertices is called a simple circuit
Bob wants to count all possible travel paths.
Define F(k) as the total number of travel paths with happiness value k, modulo 998244353.
Please find F(1)⨁F(2)⨁F(3)⨁...⨁F(L),where ⨁ represents XOR.
输入
The first line contains an integer T(T≤500) —the number of test cases.
The first line of each test case contains 3 integers n,m,L(1≤n,L≤100000,1≤m≤200000) —number of cities, number of roads, length range of roads.
The next m lines , each line contains 3 integers ui,vi,wi(1≤ui,vi≤n,1≤wi≤L) —.represents a road of length wi connecting ui,vi.
It is guaranteed that there are no double edges and self-loops.
1≤∑n,∑L≤500000,1≤∑m≤1000000
The first line of each test case contains 3 integers n,m,L(1≤n,L≤100000,1≤m≤200000) —number of cities, number of roads, length range of roads.
The next m lines , each line contains 3 integers ui,vi,wi(1≤ui,vi≤n,1≤wi≤L) —.represents a road of length wi connecting ui,vi.
It is guaranteed that there are no double edges and self-loops.
1≤∑n,∑L≤500000,1≤∑m≤1000000
输出
For each test case, output a line containing an integer representing the answer.
样例输入 复制
3
3 3 6
1 2 6
2 3 4
3 1 5
5 4 10
1 2 10
1 3 1
2 4 7
1 5 4
7 8 7
1 2 4
2 3 1
2 4 2
2 5 2
5 6 4
2 7 4
7 1 1
6 2 1样例输出 复制
2
6
47