题解：P10411 「QFOI R2」树色尤含残雨

考察简单贪心和唯一分解定理。

首先根据唯一分解定理，可得：

x = \prod_{i = 1}^k p_i^{q_i},p_i \in prime,q_i \in N^+

然后分类讨论，首先你会发现当

x

有因子是完全平方数（也就是分解之后

\exists i(1 \le i \le n)q_i>1

），那么答案除了在只有一个质因数的时候为

x

其他情况都是

1

，不分奇偶，为啥？很简单，因为就算质因子数量为奇数，也可以将其中一个拆分，变成偶数。那么如果

x

没有因子是完全平方数，那么就要看奇偶了，奇数就取最小质因数（简单贪心思想），偶数就是

1

，原理简单，不再敖述。

代码：

CPP

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

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,minn = 0,num = 0,shu = 0;
	cin >> n;
	int q = n;
	for(int i = 2;i*i<=n;++i)
	{
		if(n%i == 0)
		{
			if(!minn)
			{
				minn = i;
			}
			++num;
			int cnt = 0;
			while(n%i == 0)
			{
				++cnt;
				n/=i;
			}
			if(cnt>1)
			{
				++shu;
			}
		}
	}
	if(n>1)
	{
		if(!minn)
		{
			minn = n;
		}
		++num;
	}
	if(!shu)
	{
		if(num&1)
		{
			cout << minn;
		}
		else
		{
			cout << 1;
		}
	}
	else
	{
		if(num == 1)
		{
			cout << q;
		}
		else
		{
			cout << 1;
		}
	}
	return 0;
}

题解：P10411 「QFOI R2」树色尤含残雨

文章操作

相关推荐

评论

题解：P10411 「QFOI R2」树色尤含残雨