AcWing 3491. 完全平方数
原题链接
简单
作者:
神的在场证明
,
2024-04-05 10:49:03
,
所有人可见
,
阅读 1
C++ 代码
/*
输入一个n ,找到一个最小的x ,使n*x == 一个数的平方
可以把这个n 分解质因数,形如 q0^s0 * q1^s1 * q2^s2 ……判断上角标s是否为奇数, 若为奇数 则答案 x 为所有为奇次幂的数的底数相乘
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long //会爆int 一种特殊的防爆int方式 同时改成 signed main(){}
typedef pair<int,int> pII; //存储分解出的质因数 的 底数 和 指数
vector<pII> q;
void divide(int x){ //分解质因数
for(int i = 2; i <= x/i; i++){ //从2开始向后遍历
if(x % i == 0) { //若出现 一个可以使x除尽的数
int s = 0;
while(x % i == 0){ //判断出现几次
s++;
x /= i;
}
q.push_back({i,s});
}
}
if(x > 1) q.push_back({x,1});
}
signed main(){
ios::sync_with_stdio(false);
int n;
cin >> n;
divide(n);
int res = 1;
for(int i = 0; i < q.size(); i++){ //找到所有奇次幂的数
if(q[i].second & 1) res *= q[i].first;
}
cout << res << endl;
return 0;
}