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

Master of GCD

程序员文章站 2022-03-13 16:37:35
...

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
Master of GCD


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;

}

 

 

 

 

 

 

相关标签: innovative