Master of GCD
SDUT 2019 Autumn Team Contest 22nd
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. Thefollowingmlines,eachlinecontainsthreeintegersli (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.
Example
Explanation Forthefirsttestcase, afteralloperations, thenumberswillbe [6,6,12,6,6]. Sothegreatestcommon divisor is 6.
Page 14 of 17
思想:差分思想。(初次接触,不是很了解)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 7;
const ll mod = 998244353;
ll qpow(ll i,ll j)
{
ll ans=1;
while(j)
{
if(j&1)
{
ans=(ans*i)%mod;//注意需要队ans*i进行取模
}
i=(i*i)%mod;//注意需要对(i*i)进行取模
j=j>>1;
}
return ans;
}
int a[MAXN], b[MAXN];
int main()
{
ios::sync_with_stdio(0);
int t, n, m;
cin>>t;
while(t--)
{
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
cin>>n>>m;
int l, r, x;
while(m--)
{
cin>>l>>r>>x;
if(x == 2)
{
a[l]++;
a[r+1]--;
}
else
{
b[l]++;
b[r+1]--;
}
}
ll min1 = a[1], min2 = b[1];
for(int i = 2; i <= n; i++)
{
a[i] += a[i-1];
b[i] += b[i-1];
if(a[i]<min1) min1 = a[i];
if(b[i]<min2) min2 = b[i];
}
cout<<(qpow(2, min1)*qpow(3, min2))%mod<<endl;
//注意需要对结果进行取模
}
return 0;
}
推荐阅读
-
详解iOS多线程GCD的使用
-
SQL server无法禁用xx已将数据库存上下文更改成为master2002错误解决方法
-
phpinfo() 中 Local Value(局部变量)Master Value(主变量) 的区别
-
详解IOS中GCD的使用
-
多线程高效合作之master-warker模式
-
SQL Server移除事务日志后sys.master_files依然存在记录问题
-
Spark异常:A master URL must be set in your configuration处理记录
-
AWS Aurora数据库 Multi-Master 小测
-
【多进程】php实现 master-worker 守护多进程模式
-
罗技MX Master怎么样?罗技MX Master无线鼠标评测