C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

分解质因数

想要 n * x = m^2

m^2 意味着：m的每个质因子的次数一定是偶数,只有是偶数这个质因子才可以分成两份

因此我们只需要看一下n的质因子的次数是否是奇数，如果是奇数，那么我们就至少要乘上一个这个质因子

$时间复杂度：O(sqrt(n))$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ll n; cin >> n;

    ll res = 1;
    for (ll i = 2; i * i <= n; i ++)  // 枚举所有的质因子
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) s ++, n /= i;
            if (s % 2) res *= i;
        }
    if (n > 1) res *= n;
    cout << res;
    return 0;
}