HDU - 6273Master of GCD【一维差分】

题目

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 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. 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 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. Output 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

题意：t组输入，输入两个数n，m，分别代表数组长度，初始化数组的全部值都为1，对数组进行m次操作，每次选定一个范围,l,r,后面跟着2或3表示对【l，r】范围内的数全都乘上2或三，问这个数组的最大公约数

思路：这个最大公约数一定最后乘上的2是最少的，3也是最少的，所以我们可以用一维差分，我们开两个数组第一个表示对乘以二的数的差分，第二个表示对乘以三的差分，分别统计一下两个数组中的最小数的幂相乘就是答案，具体看代码

AC code

#include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<sstream> #include<queue> #include<stack> using namespace std; int b[111150],c[111111]; void solve() { int n,m; scanf("%d%d",&n,&m); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); int x,y,z; for(int i=0;i<m;i++)//进行差分 { scanf("%d%d%d",&x,&y,&z); if(z==2) { b[x]++,b[y+1]--; } else { c[x]++,c[y+1]--; } } int max1=b[1],max2=c[1]; for(int i=2;i<=n;i++)//前缀和 { b[i]+=b[i-1]; c[i]+=c[i-1]; max1=min(max1,b[i]); max2=min(max2,c[i]); } long long int s=1; while(max1--)//计算2的幂 { s*=2; s%=998244353; } while(max2--) { s*=3; s%=998244353; } printf("%lld\n",s); } int main() { //ios::sync_with_stdio(0); int t; scanf("%d",&t); while(t--) { solve(); } }