题面：
Problem J. Master of GCD
Hakase has n numbers in a line. At first, they are all equal to 1. Besides, Hakase is interested in primes.She will choose a continuous subsequence [l,r] and a prime parameter x each time and forevery l ≤ i ≤ r, she will change ai into ai ∗ x. To simplify the problem, x will be 2 or 3. After m operations, Hakase wants to know what is the greatest common divisorof all the numbers.
Input
The first line contains an integer T (1 ≤ T ≤10) representing the number of test cases.
For each test case, the first line contains two integers n (1 ≤ n ≤100000) and m (1≤ m ≤ 100000),where n refers to the length of the wholesequence and m means there are m operations.
The following m lines, each line contains three integers li (1 ≤ li≤ n), ri (1 ≤ ri ≤ n), xi (xi ∈{2,3}), whichare referred above.
Output
For each test case, print an integer inone line, representing the greatest common divisor of the sequence. Due to the answer might be very large,print the answer modulo 998244353.
翻译如下：
GCD问题大师
Hakase一行有n个数字。一开始，它们都等于1。此外，Hakase对质数很感兴趣。每次她都会选择一个连续子序列[l,r]和一个素数参数x，并且每次l≤i≤r时，她都会将ai变为ai * x，为了简化问题，x取2或3。经过m次运算后，Hakase想知道所有数的最大公约数是什么。
输入
第一行包含一个整数T(1≤T≤10)，表示测试用例的数量。
对于每个测试用例，第一行包含两个整数n(1≤n≤100000)和m(1≤m≤100000)，其中n表示整个序列的长度，m表示有m个操作。
下面的m行，每行包含三个整数li(1≤li≤n)， ri(1≤ri≤n)， xi (xi∈{2,3})，如上所述。
输出
对于每个测试用例，在一行中打印一个整数，表示序列的最大公约数。由于答案可能非常大，因此打印答案取模998244353。
代码：
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100010; const int mod = 998244353; LL a[N], b[N]; LL quick_pow(LL a, LL b)//快速幂算法 { LL ans = 1; while(b) { if(b & 1){ ans = (ans * a) % mod; } a = (a * a)% mod; b >>= 1; } return ans;//返回算得的 } int main() { int T; scanf("%d", &T);//测试用例数量 while(T -- ){ int n, m; scanf("%d%d", &n, &m); memset(a, 0, sizeof(a));//初始化差分数组 memset(b, 0, sizeof(b)); while(m -- ){//m 个操作 int l, r, x; scanf("%d%d%d", &l, &r, &x); if(x == 2) a[l] ++, a[r + 1] --;//若要乘的区间要乘的数为2 就让那个区间的前缀和数组+1 else if(x == 3) b[l] ++, b[r + 1] --;//若要乘的区间要乘的数为3 就让那个区间的前缀和数组+1 } LL min2 = a[1], min3 = b[1];//默认先让下标1处为最小值 for(int i = 2; i <= n; i ++ )//从下标2处开始求前缀和 { a[i] += a[i - 1], b[i] += b[i - 1];//求前缀和 min2 = min(min2, a[i]);//查找2出现的最小次数 min3 = min(min3, b[i]);//查找3出现的最小次数 } LL ans = (quick_pow(2, min2)%mod * quick_pow(3, min3) %mod)%mod;//2的最小出现次数*3的最小出现次数=最大公约数 //为什么要mod两次， 因为(a*b)%mod = ((a % mod) * (b % mod)) printf("%lld\n", ans); } }