AcWing 3491. 完全平方数(简单易懂讲解)
原题链接
简单
作者:
YAX_AC
,
2024-04-04 20:54:18
,
所有人可见
,
阅读 5
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
LL n;
LL m = 1;
int main()
{
scanf("%lld",&n);
//a*m = b*b,b*b的所有质因子的个数一定是偶数个,要想a*m = b*b,a*m的所有质因子次数也应该是偶数
//就是把a中质因子为奇数个的再加上一个,变成偶数,即所有奇数个a中的质因子相乘为m,这样a*m所有的质因子就是偶然数个了
for(LL i = 2; i<=n/i; i++)
{
if(n%i==0)
{
int s = 0;
while(n%i==0)
{
s++;
n/=i;
}
if(s%2) m*=i;
}
}
if(n>1) m*=n;
printf("%lld",m);
return 0;
}