题解：P10515 转圈

chenly8128 · 2025-02-25 21:05:27 · 题解

分析一下看似复杂的移动过程。

从 i 号节点移动一次，会到达 i + i \times m \mod n 号节点（这里 0 号节点等价于 n 号节点，这不重要），整理一下，就是到达了 i\times(m+1) \mod n 号节点。那么显然，如果移动 k 次，就会到达 i \times (m+1)^k \mod n 号节点。

题目要我们求开始循环前共走了几个格子。由于我们是从一号节点出发的，所以需要求 (m+1)^k \equiv 1 \mod n，k 的最小正整数解。

这就是求 m+1 对于 n 的阶。

由于 n 是质数，所以 \varphi(n) = n-1。于是我们可以通过用 n-1 的质因数试除，然后快速幂判断是否可行的方法，找出 m+1 对于 n 的阶。 质因数可以通过欧拉筛的方法快速找出。

复杂度预处理 O(n)，单次查询为试除和快速幂的复杂度之积 O(\log_2^2n)。总复杂度 O(n+T\log_2^2n)。

// Author: chenly8128
// Created: 2025-02-25 20:37:35

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e7;
int sf[MAXN+10],T,n,m;
vector <int> pr;
ll qpow (ll a,ll k,ll mod) {
    ll ans = 1;
    while (k) {
        if (k&1) ans = ans * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return ans;
}
int main (void) {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    sf[1] = 1;
    for (int i = 2;i <= MAXN;i++) {
        if (!sf[i]) {
            sf[i] = i;
            pr.push_back(i);
        }
        for (int j : pr) {
            if (i * j > MAXN) break;
            sf[i*j] = j;
            if (i % j == 0) break;
        }
    }
    cin >> T;
    while (T--) {
        cin >> n >> m;
        if (n == m+1) {
            cout << 2 << '\n';
            continue;
        }
        int x = n-1,ans = n-1;
        while (x > 1) {
            if (qpow(m+1,ans/sf[x],n) == 1) ans /= sf[x];
            x /= sf[x];
        }
        cout << ans << '\n';
    }
    return 0;
}