P15013 题解

I_will_AKIOI · 2026-01-24 19:11:23 · 题解

图是一个基环内向森林。由于走了 n+k 步，每个环的大小显然 \le n，因此 a 中出现的每个数肯定都在环上。

对于没有在 a 中出现过的数 i，我们把他连在环上的某个点，使得这个点走 n+k 步能到达 a_i 就行，这个点总是存在的，因此我们只需要考虑环的问题。

先把 a 中所有环找出来，长度为 L_1,L_2\dots L_m。最终的图肯定是把一些 L_j 拼在一起组成一个新环，使得环上每个点每次走 n+k 步，走 L_j 次回到原位。因此组成每个新环所有的 L 始终相等。

记录长度为 L 的环的个数 c_L。尝试推一下把几个相等的 L 拼在一起使得最少走 L 次还回到原位，假设有 b 个 L，那么总环长为 bL。

长度为 bL 的环，每次走 n+k 步，回到原位的最少步数为 a，那么有：

我们要让 a 最小，这样才能凑出 c_i 个环。因此有：

根据 \gcd(a,b)\cdot\operatorname{lcm}(a,b)=ab，我们有：

若 b\mid(n+k)，则把一个 b 提出来。

我们只需要找到最小的 b 使得上述等式成立，因为其余的解 b' 肯定都是 b 的倍数，都能用 b 凑出来。把 L 分解质因数，每个 L 的质因子 p，把 n+k 不断尝试除以 p，若能除尽就计入 b。

把 b 解出来之后，就相当于每 b 个 L 可以一起消掉，因此若对所有 L 满足 b\mid c_L 则有解，否则无解。

时间复杂度 O(\sum n\log n)。

#include<bits/stdc++.h>
#define N 500005
using namespace std;
int n,m,s,a[N],tot[N],p[N],low[N];
bool vis[N];
bitset<N>ok;
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) tot[i]=vis[i]=0;
    for(int i=1;i<=n;i++) cin>>a[i],vis[a[i]]=1;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]) continue;
        int now=a[i],cnt=1;
        vis[i]=0;
        while(now!=i)
        {
            cnt++;
            vis[now]=0;
            now=a[now];
            if(cnt>n) {cout<<"No\n";return;}
        }
        tot[cnt]++;
    }
    for(int i=1;i<=n;i++)
    {
        int now=i,tmp=n+m;
        while(now>1)
        {
            while(tmp%low[now]==0) tmp/=low[now];
            now/=low[now];
        }
        tmp=(n+m)/tmp;
        if(tot[i]%tmp) {cout<<"No\n";return;}
    }
    cout<<"Yes\n";
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    for(int i=2;i<=500000;i++)
    {
        if(!ok[i]) p[++s]=i,low[i]=i;
        for(int j=1;j<=s&&i*p[j]<=500000;j++)
        {
            ok[i*p[j]]=1;
            low[i*p[j]]=p[j];
            if(i%p[j]==0) break;
        }
    }
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}