J 离散数学

思路

可以很容易的发现，以 $A$ 为生成元，会生成一个循环群 $G$，而 $P$ 必在 $G$ 中。

题目要求：已知 $P^k = A$，且 $k$ 为质数，求$P$。

假设 $P$ 存在，以 $P$ 为生成元，生成的循环群 $G$ 中必有 $A$，而 $A=P^{k\mod|G|}$，假设 $k$ 关于 $|G|$ 的逆元为 $k^{-1}$，那么：

$(A)^{k^{-1}} = (P^{k\mod|G|})^{k^{-1}} = P^{k\times k^{-1} \mod |G|}=P$

因此 $P=A^{k^{-1}}$

我们发现，$P$ 不存在，当且仅当逆元 $k^{-1}$ 不存在，而 $k$ 总是质数，因此 $P$ 恒存在。

然后就很简单了，因为$G$必定是由一些环构成的，我们可以求出每个环的大小 $r_i$ 和元素 $R_i$。由于单位元为 $[1,2,3,…,n]$，那么 $P_{R_{i,j}}=R_{i, (j + k^{-1})\mod r_i}$，代表 $P$ 的第 $R_{i,j}$ 个位置应该是 $R_{i, (j + 1/k)\mod r_i}$

时间复杂度 $O(n)$

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;

ll ex_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll gcd = ex_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return gcd;
}

ll inv(ll a, ll mod) {
    ll x, y;
    ex_gcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}

int a[N], p[N];
bool vis[N];
vector<int> c;

void dfs(int u) {
    if (!vis[u]) {
        vis[u] = 1;
        c.emplace_back(u);
        dfs(a[u]);
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) 
        cin >> a[i];

    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) {
            c.clear();
            dfs(i);
            int r = c.size();
            int w = inv(k, r);
            for (int i = 0; i < r; ++i) 
                p[c[i]] = c[(i + w) % r];
        }
    }

    for (int i = 1; i <= n; ++i) 
        cout << p[i] << ' ';
    
    cout << endl;
    return 0;
}