1 solutions

  • 0
    @ 2023-2-7 15:23:46

    该题是一道融合了差分与快速幂的综合运用题

    我们只需要求对于n个1,他们分别乘了多少个2、分别乘了多少个3,假设它们每个数至少都乘了t2个2,t3个3,那么最大公约数即为(2^t2*3^t3)%999999998,即求他们公共扩大了多少倍。

    而2的t2次方,3的t3次方,就涉及了快速幂的知识点了。

    那怎么知道每个数乘了多少个2和3呢?这时我们就可以想到数组,用两个数组将每个数分别乘了多少个2、3储存下来,这时对于储存的方法,我们就要想到差分数组,来求前缀和来得到每个位置分别乘了多少个2、3

    详情见代码,本身题并不难,可能对于小白来说想不到差分,这种情况只能菜就多练练

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll N=1e5+5; 
    const ll M=999999998;
    //快速幂
    ll quick(ll x,ll y){    
    	ll z=1;
    	while(y!=0){
    		if(y%2==1){
    			z=(z*x)%M;
    		}
    		x=(x*x)%M;
    		y=y/2;
    	}
    	return z%M;//z%M即为2的t2或3的t3次方取与的结果了 
    }
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		int n,m;
    		scanf("%d %d",&n,&m);
    		int a2[N],a3[N];
            int b2[N],b3[N];
            memset(a2,0,sizeof(a2));
            memset(a3,0,sizeof(a3)); 
            memset(b2,0,sizeof(b2));
            memset(b3,0,sizeof(b3));//不知道这个函数的可自行查阅,在这里只是起一个初始化的作用
    		while(m--){    
    			ll l,r,x;
    			scanf("%lld %lld %lld",&l,&r,&x);
    			if(x==2){
    				a2[l]++;
    				a2[r+1]--;
    			}else{
    				a3[l]++;
    				a3[r+1]--;
    			}
    		}
    	    int t2=a2[1],t3=a3[1];
    	    for(ll i=1;i<=n;i++){   //差分,本题重点
    		    b2[i]=b2[i-1]+a2[i];
    		    t2=min(t2,b2[i]);
    		    b3[i]=b3[i-1]+a3[i];
    		    t3=min(t3,b3[i]);
    	    }
    	    ll c=quick(2,t2)*quick(3,t3)%M;   
    	    printf("%lld\n",c);
        }
    	return 0;
    }
    • 1

    Information

    ID
    6686
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    16
    Accepted
    5
    Uploaded By