欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

HDU6273 Master of GCD【差分数组】

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
*/