P8754 [蓝桥杯 2021 省 AB2] 完全平方数 题解

· · 题解

1.分析：

首先我们需要了解唯一分解定理。这个定理简单来说就是对于任意一个数 n，它都可以分解为若干个质数的乘积。 比如 60 就可以分解为 2^2\times 3\times 5。

如果一个数是完全平方数，那么这若干个质数的指数都一定是偶数。比如：36=2^2\times 3^2=(2\times 3)^2=6^2。

所以，我们先将读入的 n 进行质因数分解。对于分解的每一个质数，如果它的指数为奇数，则 x 的因子就必须有这个质数。

2.AC 代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p[1000],g[1000],cnt,ans;
int main(){
    cin>>n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0) cnt++;
        while(n%i==0){
            p[cnt]=i;//p是质因子
            g[cnt]++;//g是这个质因子的指数
            n/=i;
        }
    }
    if(n>1){
        p[++cnt]=n;
        g[cnt]++;
    }
   //以上是质因数分解模板
    ans=1;
    for(int i=1;i<=cnt;i++){
        if(g[i]%2){//如果指数是奇数
            ans*=p[i];//那么就要补一个这个质数
        }
    }
    cout<<ans;
    return 0;
}