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

· · 题解

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

首先，要使 nx 为完全平方数，需要知道完全平方数的一个性质：完全平方数的质因子的指数一定为偶数。

证明：

设 \sqrt{nx}=b ，b 是正整数，则根据唯一分解定理，可得：

b=p_{1}^{k_{1}}\times p_{2}^{k_{2}}\times p_{3}^{k_{3}}\times ... \times p_{r}^{k_{r}}

其中 p_{1},p_{2},p_{3}...p_{r} 为质数。

由完全平方数的定义，这个完全平方数 nx 为 b^2 ，即：

nx=(p_{1}^{k_{1}}\times p_{2}^{k_{2}}\times p_{3}^{k_{3}}\times ... \times p_{r}^{k_{r}})^2

把括号拆开，得到

nx=p_{1}^{2k_{1}}\times p_{2}^{2k_{2}}\times p_{3}^{2k_{3}}\times ... \times p_{r}^{2k_{r}}

可以看到，每个质因子的指数均为 2k_{m} ，必然是偶数。

所以，可以得到这样一个思路：

对 n 进行质因数分解，若质因子指数为偶数，对结果无影响。若质因子指数为奇数，则在 x 中乘以这个质因子，保证指数为偶数。

最后是完整代码：

#include <bits/stdc++.h>
using namespace std;
long long n,ans=1;
int main()
{
    scanf("%lld",&n);
    for(long long i=2;i*i<=n;i++)
        {
            int cnt=0; //cnt计数，表示质因子pri[i]的指数
            while(!(n%i))cnt++,n/=i;
            if(cnt%2)ans*=i; //如果指数不是偶数，在x中要有一个这个质因子，保证指数为偶数
        }
    if(n!=1)ans*=n;//注意n没分尽的情况
    printf("%lld",ans);
    return 0;
}

AC记录