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

linjinkun · 2025-10-21 13:27:15 · 题解

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

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

然后分类讨论，首先你会发现当 x 有因子是完全平方数（也就是分解之后 \exists i(1 \le i \le n)q_i>1），那么答案除了在只有一个质因数的时候为 x 其他情况都是 1，不分奇偶，为啥？很简单，因为就算质因子数量为奇数，也可以将其中一个拆分，变成偶数。那么如果 x 没有因子是完全平方数，那么就要看奇偶了，奇数就取最小质因数（简单贪心思想），偶数就是 1，原理简单，不再敖述。

代码：

#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;
}