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

HDU-6273 Master of GCD (素因子分解定理应用)

程序员文章站 2022-03-04 22:41:52
...

HDU-6273 Master of GCD (素因子分解定理应用)

HDU-6273 Master of GCD (素因子分解定理应用)


题意:

  • 给 T 组数据
  • 每组数据第一行输入 n 和 m ,表示对一个长度为 n ,初始值值为 1 的数组,进行 m 次 操作
  • 每次操作输入 L ,R ,op 三个数,op 只能为 2 或 3,表示 L 到 R 区间的每个数字 a[i] = a[i] * op ,i=2,3
  • 求 m 次操作后,这 n 个数的最大公约数是多少

思路:

  • 要想求 n 个数的最大公约数,可以将这 n 个数进行素因子分解,然后找出这 n 个分解式子中 所有出现过的素因子 a 与 该素因子的最小次幂 p ,然后将所有的 ap 相乘即为最大公约数
  • 由题意可知,每个数的初始值为1,素因子只可能是 2 或 3,所以就记录 a[i] 乘了多少次2 和多少次 3 就相当于把 a[i] 素因子分解了,最后去统计 2 的最小次幂和 3的最小次幂 然后相乘 (可用快速幂,记得取余)
  • 怎么统计 a[i] 乘了多少次 2 和 3 呢? 我用的是扫描线的思想,用book数组统计,book[L]++, book[R+1]–,最后计算前缀和

撸代码:

#include<math.h>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
long long book[4][100010];
long long mod=998244353;
ll Quick_Power(ll a,ll b)//快速幂
{
    ll res = 1;
    a %= mod;
    while(b){
        if(b&1){
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res%mod;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=0;i<=n+1;i++){
			book[2][i]=book[3][i]=0;
		}
		int r,l,tag;
		for(int i=0;i<m;i++){
			scanf("%d%d%d",&l,&r,&tag);
			book[tag][l]++;
			book[tag][r+1]--;
		}
		
		for(int i=1;i<=n;i++){
			book[2][i]+=book[2][i-1];
			book[3][i]+=book[3][i-1];
			/*由于初始值为 1 ,所以每个数的素因子只有 2 和 3 ,
			通过该步骤得出每个数的素因子的幂次,找到2的最小幂次 和 3 的最小幂次,
			乘积就是最大公约数  */
//			printf("%d  |   %d\n",book[2][i],book[3][i]);  
			
		}
		long long mina=0x3f3f3f3f,minb=0x3f3f3f3f;
		for(int i=1;i<=n;i++){
			mina=min(mina,book[2][i]);
			minb=min(minb,book[3][i]);
		}
		long long temp1=Quick_Power(2,mina);
		long long temp2=Quick_Power(3,minb);
		printf("%lld\n",(temp1*temp2)%mod);
	}
	return 0;
}