自动搬运

查看原文

来自洛谷，原作者为

	chenly8128 God helps those who help themselves.

搬运于2025-08-24 22:58:46，当前版本为作者最后更新于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;
}