题目描述

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 ，且区间内的每一个数都是1，然后一共有 m 组数据，每组为L R X；这个[L ,R]闭区间内的数都乘以 X； 问你最后这一串数字的最大公约数，并且最后结果对 998244353取模；

解题思路

这个题就是一个差分数组，因为这数列的最大公约数就是这个数列 2 的 出现 2的最少次数的幂 乘以 3 的出现3的最少次数的幂 将2和3分开讨论，然后分别记录这个区间内最少出现了几次2或3；再利用矩阵快速幂进行计算，最后把两个结果相乘再取模就行了；

#include<iostream>
#include<algorithm>

using namespace std;
#define ll long long
const int maxn=1e5+10;
const int mod=998244353;
ll a[maxn],b[maxn],c[maxn];
//矩阵快速幂 
ll poww(ll x,ll y)
{
	ll da=1;
	while(y)
	{
		if(y&1) da=(da*x)%mod;
		x=x*x%mod;
		y>>=1;
	}
	return da;
}

int main()
{
	ios::sync_with_stdio(false);
	int t,m,n;
	ll x,y,z;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=0;i<=n;i++) b[i]=c[i]=0;
// 数组 b[]记录 2；的情况
// 数组 c[]记录3；的情况 
 		while(m--)
		{
			cin>>x>>y>>z;
// 差分的关键代码 
			if(z==2)
			{
				b[x]++,b[y+1]--;
			}
			else c[x]++,c[y+1]--;
		}
		ll sum=0;
		ll ans,ans2;
		ans2=ans=10000000;
// 记录这个数组内最少出现了多少 2 
		for(int i=1;i<=n;i++)
		{
			sum+=b[i];
			ans=ans<sum?ans:sum;
		}
// 记录这个数组内最少出现了多少 3 
		sum=0;
		for(int i=1;i<=n;i++)
		{
			sum+=c[i];
			ans2=ans2<sum?ans2:sum;
		}
//分别求 2 和 3 的幂然后相乘 
		sum=poww(2,ans);
		ans=sum%mod*(poww(3,ans2))%mod;
		cout<<ans<<"\n";
	}
	return 0;
}
/* 2 5 3 1 3 2 3 5 2 1 5 3 6 3 1 2 2 5 6 2 1 6 2 */