题解：SP8057 AMR10C - Square Free Factorization

HJC_666 · 2024-08-26 21:14:33 · 题解

题目大意：

这道题就是让我们去分解质因数，求出出现次数最多的质因子的数量。

解题方法：

我们首先将这个数进行分解质因数，具体的过程如下：

int maxn=INT_MIN;//记录每一个数的答案

for(int i=2;i*i<=n;i++){
    int cnt=0;//记录下每一个质因子的数量
    if(n%i==0){
        while(n%i==0){//如果是它的质因子就一直除下去。
            cnt++;//将他的数量增加
            n/=i;//分解
        }
    }
    if(cnt>maxn){//如果这个质因子的数量大于了最多的质因子数量。就更新答案
        maxn=cnt;
    }
}
if(n!=1){//这里说明没有除完。
  maxn=max(maxn,1);
}

这样我们就得到了每一个数的答案。

完整代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        int maxn=INT_MIN;
        for(int i=2;i*i<=n;i++){
            int cnt=0;
            if(n%i==0){
                while(n%i==0){
                    cnt++;
                    n/=i;
                }
            }
            if(cnt>maxn){
                maxn=cnt;
            }
        }
        if(n!=1){
            maxn=max(maxn,1);
        }
        cout<<maxn<<'\n';
    }
    return 0;
}

完结撒花。