【HDU6273】Master of GCD（思维）

题目链接

 

【题意】

给出T组数据（1 <= T  <= 10）,每组数据中，有两个数n（1  <= n <= 10^5）和 m (1 <= m <= 10^5)。其中 n 表示有n个由1组成的数， m表示下面给出m组数据，每组数据由 p，q，k 组成。表示区间p 到 q，增大k倍（k 等于2 或者 3）.输出这n个数最终的最大公约数。由于数据比较大，因此需要mod 998244353。  

【解题思路】

难点：2出现的最少次数和3出现的最少次数的乘积就是它们的最大公约数。

这句话刚开始看题解我也觉得理解不了，但后来一想感觉确实有道理，加入说一段区间乘上5个2，另一段区间（元素有相交也没关系）乘上2个2，那么他们的最大公约数肯定是4，所以只要看出现的最少次数就可以了。

那么这里运用差分的思想计算2和3出现的个数（其实就是树状数组区间更新……但是这里可以直接用一个数组做），将2的个数和3的个数分开计算，假如1-3的位置需要乘2，那么记录2的个数的数组1的位置+1，4的位置-1。55555之前看过树状数组区间更新这个其实就不难理解了。

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=998244353;
LL a[maxn],b[maxn];
LL quick_pow(LL a,LL b)
{
    LL ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ans%MOD;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        while(m--)
        {
            int x,y,c;
            scanf("%d%d%d",&x,&y,&c);
            if(c==2)
            {
                a[x]++;
                a[y+1]--;
            }
            else
            {
                b[x]++;
                b[y+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];
            min1=min(min1,a[i]);
            min2=min(min2,b[i]);
        }
        LL sum=quick_pow(2,min1)%MOD*quick_pow(3,min2)%MOD;
        printf("%lld\n",sum);
    }
    return 0;
}