題目描述

Hakase has n numbers in a line. At fi rst, 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 for every 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 divisor of all the numbers.

?

輸入

The first line contains an integer T (1≤T≤10) representing the number of test cases.
For each test case, the fi rst line contains two integers n (1≤n≤100000) and m (1≤m≤100000),where n refers to the length of the whole sequence 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} ),which are referred above.

?

輸出

For each test case, print an integer in one line, representing the greatest common divisor of the sequence. Due to the answer might be very large, print the answer modulo 998244353.

?

樣例輸入

復制樣例數據

2
5 3
1 3 2
3 5 2
1 5 3
6 3
1 2 2
5 6 2
1 6 2

樣例輸出

6
2

?

提示

For the first test case, after all operations, the numbers will be [6,6,12,6,6]. So the greatest common divisor is 6.

?

題目大意：

先輸入一個整數t，代表有t組測試，對于每組測試，第一行輸入兩個整數n,m，n代表數組的長度，m代表下面對這個數組進行m此操作，下面m行每行輸入三個整數l,r,x，代表將數組從a[l]到a[r]里面每一個數進行乘x操作，x只取2,3兩個值，問最后整個數組的最大公約數是多少。

解題思路：

因為只是對數組的某段區間進行乘2或乘3操作，所以可以通過計算數組的每一項元素乘2，乘3的次數，找出最小乘2次數n1，乘3的次數n2，最后的結果就是(2^n1)*(3^n2)，所以我們可以通過差分數組進行區間修改的維護，O(1)修改，O(n)查詢，最后通過快速冪計算出乘積即可。

代碼：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 998244353.;
int d1[100100],d2[100100];
ll quickpow(ll base,ll x) {ll ans=1;while(x) {if(x&1) ans=(ans*base)%mod;base=(base*base)%mod;x>>=1;}return ans;
}
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int t;cin>>t;while(t--) {int n,m;cin>>n>>m;fill(d1+1,d1+1+n,0);fill(d2+1,d2+1+n,0);for(int i=1;i<=m;i++) {int a,b,c;cin>>a>>b>>c;if(c==2) d1[a]++,d1[b+1]--;if(c==3) d2[a]++,d2[b+1]--;}ll nape1=0,nape2=0;ll maxl1=inf,maxl2=inf;for(int i=1;i<=n;i++) {nape1+=d1[i];nape2+=d2[i];maxl1=min(maxl1,nape1);maxl2=min(maxl2,nape2);}ll ans=(quickpow(2LL,maxl1)*quickpow(3LL,maxl2))%mod;cout<<ans<<endl;}return 0;
}

?