[蓝桥杯 2021 省 AB2] 完全平方数

一、题目描述

P8754 [蓝桥杯 2021 省 AB2] 完全平方数

二、问题简析

2.1 唯一分解定理

唯一分解定理：大于1的自然数都可以唯一地写成素数的积。

由该定理，一个大于 $1$ 的自然数 $b$ 可以表示为 $b=a_1^{p_1}\ast a_2^{p_2}\ast ...\ast a_n^{p_n}$ ($a_1,a_2,...,a_n$ 为素数；$p_1,p_2,...,p_n$ 为对应的指数，即有 $p_n$ 个该数)。该自然数 $b$ 的平方为 $b^2=a_1^{2p_1}\ast a_2^{2p_2}\ast ...\ast a_n^{2p_n}$，所有的指数都是偶数。
我们可以得到，若一个自然数是完全平方数，则将该自然数写出素数的积后，每个素数的指数一定是偶数。

因此，我们可以分解 $n$，将指数不为偶数的素数相乘，就得到了 $x$。

2.2 分解自然数

以下代码给出了如何将大于 $1$ 的自然数分解为素数的积。

// 将整数n分解成若干个素数，除1和本身
map<int, int> factors(int n)
{
    map<int, int> ans;      // 分解n后，有ans[i]个i
    // n==1，特殊考虑
    if (n == 1)
    {
        ans[n] = 1;
        return ans;
    }
    // 1和本身总是因数，这里忽略
    for (int i = 2; i * i <= n; i++)
    {
        // 可能有若干个i
        while (n % i == 0)
        {
            ans[i]++;       // 分解出一个i
            n /= i;
        }
    }
    if (n != 1)             // n==1，已经分解完了
        ans[n] += 1;
    return ans;
}

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int quickin(void)
{
	int ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}



int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	ll n, ans = 1;
	cin >> n;
	if (n == 1)
	{
		cout << 4 << endl;
		return 0;	
	}
	
	for (ll i = 2; i * i <= n; i++)
	{
		ll cnt = 0;
		while (n % i == 0)
		{
			cnt += 1;
			n /= i;	
		}
		if (cnt % 2 != 0)    ans *= i;
	}
	if (n != 1)    ans *= n;
	
	cout << ans << endl;
	
	return 0;
}

完