P8754-蓝桥杯-2021-省-AB2-完全平方数-题解
P8754 [蓝桥杯 2021 省 AB2] 完全平方数 题解
首先，要使
n x nx
n
x 为完全平方数，需要知道完全平方数的一个性质： 完全平方数的质因子的指数一定为偶数 。
证明：
设
n x
b \sqrt{nx}=b
n
x
=
b ，
b b
b 是正整数，则根据唯一分解定理，可得：
b
p 1 k 1 × p 2 k 2 × p 3 k 3 × . . . × p r k r b=p_{1}^{k_{1}}\times p_{2}^{k_{2}}\times p_{3}^{k_{3}}\times … \times p_{r}^{k_{r}}
b
=
p
1
k
1
×
p
2
k
2
×
p
3
k
3
×
…
×
p
r
k
r
其中
p 1 , p 2 , p 3 . . . p r p_{1},p_{2},p_{3}…p_{r}
p
1
,
p
2
,
p
3
…
p
r
为质数。
由完全平方数的定义，这个完全平方数
n x nx
n
x 为
b 2 b^2
b
2 ，即：
n x
( p 1 k 1 × p 2 k 2 × p 3 k 3 × . . . × p r k r ) 2 nx=(p_{1}^{k_{1}}\times p_{2}^{k_{2}}\times p_{3}^{k_{3}}\times … \times p_{r}^{k_{r}})^2
n
x
=
(
p
1
k
1
×
p
2
k
2
×
p
3
k
3
×
…
×
p
r
k
r
)
2
把括号拆开，得到
n x
p 1 2 k 1 × p 2 2 k 2 × p 3 2 k 3 × . . . × p r 2 k r nx=p_{1}^{2k_{1}}\times p_{2}^{2k_{2}}\times p_{3}^{2k_{3}}\times … \times p_{r}^{2k_{r}}
n
x
=
p
1
2
k
1
×
p
2
2
k
2
×
p
3
2
k
3
×
…
×
p
r
2
k
r
可以看到，每个质因子的指数均为
2 k m 2k_{m}
2
k
m
，必然是偶数。
所以，可以得到这样一个思路：
对
n n
n 进行质因数分解， **若质因子指数为偶数，对结果无影响。若质因子指数为奇数，则在
x x
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;
}