分析题意与解题方法

题目描述

给定 $N$ 种颜色的珠子，形成一条由 $N$ 颗珠子组成的圆形项链。需要计算可以生产的不同种类的项链数量，忽略旋转对称性。最终输出结果取模 $P$。

输入：

• 测试用例数量 $T$。
• 每个测试用例包含两个整数 $N$ 和 $P$，其中 $1 \leq N \leq 10^{10}$，$1 \leq P \leq 30000$。

输出：

• 对于每个测试用例，输出一行结果。

---

解题思路

1. Burnside 引理

根据 Burnside 引理，圆形项链的不同排列数等于所有旋转操作下保持不变的排列数的平均值。对于长度为 $N$ 的项链，旋转操作的总数为 $N$。

不变排列数计算

对于每次旋转 $k$（$0 \leq k < N$），若项链在旋转后保持不变，则必须满足：

$$\text{gcd}(N, k) = 1$$

即旋转步数 $k$ 必须与 $N$ 互质。

总排列数

对于每个互质的 $k$，排列数为：

$$\text{排列数} = \phi(N)$$

其中 $\phi(N)$ 是 $N$ 的欧拉函数，表示小于 $N$ 且与 $N$ 互质的正整数个数。

因此，总的不同的项链数量为：

$$\text{总排列数} = \frac{\phi(N)}{N} \times N! \mod P$$

---

2. 快速计算欧拉函数

通过分解质因数计算欧拉函数：

$$\phi(N) = N \prod_{p|N} \left( 1 - \frac{1}{p} \right) $$

其中 $p$ 是 $N$ 的质因数。

代码中通过预处理质数表，利用线性筛法计算欧拉函数。

---

3. 快速幂取模

为了计算 $N! \mod P$，使用快速幂算法：

int qpow(int a, int b, int m) {
    a %= m;
    int r = 1;
    while (b) {
        if (b & 1) r = r * a % m;
        b >>= 1;
        a = a * a % m;
    }
    return r % m;
}

4. 主程序流程

初始化质数表。 对每个测试用例： 读取 $N$ 和 $P$。 计算 $\phi(N)$。 计算 $N! \mod P$。 输出结果。

标程

#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define LL long long
#define PI acos(-1.0)
#define N 33333

// 是否为素数标记数组
bool isp[N + 10];
vector<int> prime;

// 初始化素数表
void init() {
    int m = sqrt(N + 0.5);
    for (int i = 2; i <= N; i++) {
        if (!isp[i]) {
            prime.push_back(i);
            for (int j = i * i; j <= N; j += i) isp[j] = 1;
        }
    }
}

// 快速幂取模
int qpow(int a, int b, int m) {
    a %= m;
    int r = 1;
    while (b) {
        if (b & 1) r = r * a % m;
        b >>= 1;
        a = a * a % m;
    }
    return r % m;
}

// 计算欧拉函数
int euler(int n) {
    int m = sqrt(n + 0.5);
    int ans = n;
    for (int i = 0; prime[i] <= m; ++i) {
        if (n % prime[i] == 0) {
            ans = ans / prime[i] * (prime[i] - 1);
            while (n % prime[i] == 0) n /= prime[i];
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans % mod;
}

int main() {
    int t, n, i, j, k, d;
    init();
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &mod);
        int ans = 0;
        for (i = 1; i * i < n; ++i) {
            if (n % i == 0) {
                (ans += (euler(n / i) * qpow(n, i - 1, mod) % mod)) %= mod;
                (ans += (euler(i) * qpow(n, n / i - 1, mod) % mod)) %= mod;
            }
        }
        if (i * i == n) (ans += (euler(i) * qpow(n, i - 1, mod) % mod)) %= mod;
        cout << ans << endl;
    }
    return 0;
}