AcWing 3491. 完全平方数
原题链接
简单
作者:
m_math
,
2024-04-12 15:47:05
,
所有人可见
,
阅读 12
分解质因数,想办法让每个质因数的指数都为偶数即可
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
LL n;
LL x = 1;
vector<PLL> nums;
int main()
{
cin >> n;
for(LL i = 2;i <= n / i;i++)
if(n % i == 0)
{
LL cnt = 0;
while(n % i == 0)
n /= i,cnt++;
nums.push_back({i,cnt});
}
if(n > 1) nums.push_back({n,1});
// for(auto k : nums)
// printf("%d %d\n",k.first,k.second);
for(auto k : nums)
if(k.second % 2 != 0) x *= k.first;
cout << x << endl;
return 0;
}