题目分析

贴一个别人的题解

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

不会快速幂的可以参考这篇文章

参考代码

用cin，cout竟然会T

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, MOD = 998244353;
long long cnt2[N], cnt3[N];

long long qpow(long long a, long long n)
{
	if (n == 0) return 1;
	long long ans = 1;
	while (n)
	{
		if (n & 1) ans = ans * a % MOD;
		n >>= 1;
		a = a * a % MOD;
	}
	return ans % MOD;
}

int main()
{
	int t;
	scanf("%d", &t);
	
	while (t -- )
	{
		memset(cnt2, 0, sizeof cnt2);
		memset(cnt3, 0, sizeof cnt3);
		long long n, m;
		scanf("%lld%lld", &n, &m);
		while (m -- )
		{
			long long l, r, x;
			scanf("%lld%lld%lld", &l, &r, &x);
			if (x == 2) cnt2[l] ++, cnt2[r + 1] --;
			else cnt3[l] ++, cnt3[r + 1] --;
		}
		
		long long min2 = cnt2[1], min3 = cnt3[1];
		for (int i = 2; i <= n; i ++ )
		{
			cnt2[i] += cnt2[i - 1];
			cnt3[i] += cnt3[i - 1];
			min2 = min(min2, cnt2[i]);
			min3 = min(min3, cnt3[i]);
		}
		
		long long ans = qpow(2, min2) * qpow(3, min3) % MOD;
		printf("%lld\n", ans % MOD);
	}
	
	return 0;
}