HDU6273 Master of GCD【差分数组】
程序员文章站
2022-03-13 16:01:36
...
Master of GCD
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3079 Accepted Submission(s): 1129
Source
2017中国大学生程序设计竞赛-杭州站-重现赛(感谢浙江理工)
问题链接:HDU6273 Master of GCD
问题简述:(略)
问题分析:
长度为n值为1的区间,进行m次操作,每次将从l到r的区间乘以x,其中x为2或3。问最后整个区间的最大公约数是多少?结果值比较大,需要做个998244353的模除。
结果必区间2的最小次方和3的最小次方的乘积,再进行模除的结果,需要使用快速模幂计算。
程序说明:(略)
参考链接:(略)
题记:(略)
AC的C++语言程序如下:
/* HDU6273 Master of GCD */
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int M = 998244353;
const int N = 100000;
int d[2][N + 2];
// 快速模幂
LL powmod(LL x, LL n, LL m)
{
LL result = 1;
for(; n; n >>= 1) {
if(n & 1) {
result *= x;
result %= m;
}
x *= x;
x %= m;
}
return result;
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
int n, m;
memset(d, 0, sizeof(d));
scanf("%d%d", &n, &m);
while (m--) {
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
if (x == 2) d[0][l]++, d[0][r + 1]--;
if (x == 3) d[1][l]++, d[1][r + 1]--;
}
int min2 = INT_MAX, min3 = INT_MAX;
for (int i = 1; i <= n; i++) {
min2 = min(min2, d[0][i] += d[0][i - 1]);
min3 = min(min3, d[1][i] += d[1][i - 1]);
}
printf("%lld\n", powmod(2, min2, M) * powmod(3, min3, M) % M);
}
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
*/
推荐阅读
-
EC-final2017 J - Straight Master Gym - 101775J(差分,贪心)
-
2017-2018 ACM-ICPC Asia East Continent League Final J. Straight Master(差分+思维)
-
J - Straight Master Gym - 101775J ----差分
-
Straight Master Gym-101775J (差分)
-
Straight Master Gym - 101775J (差分的应用)
-
Gym - 101775J Straight Master——差分
-
洛谷P3246 [HNOI2016]序列(离线 差分 树状数组)
-
【数字_ID】HDU6274 Master of Sequence(二分+树状数组+预处理)
-
差分详解+树状数组扩展
-
【每日一题】9月15日题目精讲(二分+差分数组)