杂题——转圈

转圈

原题

题目描述

小 $\delta$ 喜欢转圈圈。

他有一个圈，被均匀分成了 $n$ 个格子，神奇的是，$n$ 是一个质数。第 $i$ 个格子上写着一个数 $i \times m$，他现在站在第一个格子上。

接下来他会看看脚下踩着的数是多少，然后向前走这么多格。他会一直反复这么做。

求最终被小 $\delta$ 踩到过的格子的数量。由于小 $\delta$ 有很多圈圈，所以他会问你很多次。

输入格式

第一行包含一个正整数 $T$，代表询问次数。

对于每组询问，输入一行两个正整数 $n,m$。

输出格式

对于每次询问，输出一行一个正整数，代表被踩到的格子的数量。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
6
5 2
11 10
17 12
23 8
31 12
9999901 114514

样例输出 #1

1
2
3
4
5
6
4
2
4
11
30
16260

提示

【样例解释】

以第一次询问为例，小 $\delta$ 依次经过的格子编号为 $1 \to 3 \to 4 \to 2 \to 1 \to \cdots$，因此被踩到过的格子个数为 $4$。

【数据范围】

  • 对于 $20%$ 的数据，$n \le 10^3$，$T \le 2 \times 10^3$。
  • 对于另外 $40%$ 的数据，$T \le 3 \times 10^3$。
  • 对于另外 $40%$ 的数据，无特殊性质。

对于所有数据，$1 \le m < n \le 10^7$，$1 \le T \le 4 \times 10^5$。保证 $n$ 是质数。

思路

​ 首先,第一步就是数学公式推导出我们跳了 k 次之后我们一共跳的各自数量$(m + 1)^{k}$,这个推导很简单,就不推导了.

​ 紧接着,第二步我们可以很简单分析出来我们最终需要求的就是对于最小的 k 满足下列公式 $s^k≡1(mod\ n)$.

​ 下面就是如何寻找这个数了,其实也还好,就是依次对于n - 1的质因子p检验$s^{\frac{p}{t}}$是否mod n余1,如果是则$t\ <-\ \frac{p}{t}$,最终的t就是答案了.这些质因子就需要使用线性埃式筛法来选取了.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>


// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;

const int INF = 1e9;
const int V = 1e7;
int T, n, m;
int lpri[10000005], pri[1000005], cnt;
bool chk[10000005];
LL QPow(LL a, LL b, LL P) {
	LL res = 1;
	for (; b; b >>= 1) {
		if (b & 1) res = res * a % P;
		a = a * a % P;
	}
	return res;
}
int fac[65], fC;

void solve() {
 	scanf("%d", &T);
	for (int i = 2; i <= V; i++) {
		if (!chk[i]) {
			pri[++cnt] = i;
			lpri[i] = i;
		}
		for (int j = 1; j <= cnt && 1ll * i * pri[j] <= V; j++) {
			lpri[i * pri[j]] = pri[j];
			chk[i * pri[j]] = true;
			if (i % pri[j] == 0) break;
		}
	}
	while (T--) {
		scanf("%d%d", &n, &m), m++;
		assert(!chk[n]);
		if (m == n) {
			puts("2");
			continue;
		}
		int t = n - 1;
		fC = 0;
		while (t > 1) fac[++fC] = lpri[t], t /= lpri[t];
		int ans = n - 1;
		for (int i = 1; i <= fC; i++) if (QPow(m, ans / fac[i], n) == 1) ans /= fac[i];
		printf("%d\n", ans);
	}
}


int main()
{
    // IOS;
    int _ = 1;
    // cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}