题目分析

给定 $b$ 和 $p$，求最小的正整数 $k$，使得对于任意 $b$ 进制数，按每 $k$ 位分段处理后，原数与结果数要么同时是 $p$ 的倍数，要么同时不是 $p$ 的倍数。

核心思路

1. 问题转化

经过数学推导，问题转化为寻找最小的 $k$ 满足：

• $b^k \equiv 1 \pmod{p}$ 或 $b^k \equiv -1 \pmod{p}$

2. 关键观察

• 如果 $\gcd(b, p) \neq 1$，直接输出 -1
• 否则计算 $b$ 模 $p$ 的乘法阶 $\delta$
• 检查是否存在 $k$ 使得 $b^k \equiv -1 \pmod{p}$，这要求 $\delta$ 是偶数且 $b^{\delta/2} \equiv -1 \pmod{p}$

算法实现详解

1. 质因数分解

vector<pair<ll, int>> work(ll x) {
    vector<pair<ll, int>> vec;
    ll t = x;
    // 试除法分解质因数
    for (int i = 2; (ll)i * i <= x; ++i) {
        if (t % i == 0) {
            int cnt = 0;
            while (t % i == 0) {
                ++cnt;
                t /= i;
            }
            vec.epb(i, cnt);
        }
    }
    if (t != 1) {
        vec.epb(t, 1);
    }
    return vec;
}

2. 欧拉函数计算

d_p = work(p);
phi_p = 1;
for (auto it : d_p) {
    phi_p *= it.fir - 1;          // φ(n) = n * ∏(1 - 1/p_i)
    L(i, 1, it.sec - 1) phi_p *= it.fir;
}

3. 乘法阶计算

ll delta = phi_p;
// 在φ(p)的因子中寻找最小的阶
for (auto it : d_phi_p) {
    while (delta % it.fir == 0 && getPow(b, delta / it.fir) == 1) {
        delta /= it.fir;
    }
}

4. 答案判定

if (__gcd(b, p) != 1) {
    cout << "-1\n";  // b与p不互质，无解
    continue;
}

if (delta % 2 == 0 && getPow(b, delta / 2) == p - 1) {
    k = delta / 2;  // 找到b^k ≡ -1 (mod p)
} else {
    cout << "-1\n";  // 不存在满足条件的k
    continue;
}

关键算法

1. 质因数分解

• 使用试除法分解 $p$ 和 $\phi(p)$
• 为后续计算欧拉函数和乘法阶做准备

2. 欧拉函数计算

• $\phi(p) = p \times \prod\limits_{i=1}^r (1 - \frac{1}{p_i})$
• 用于确定乘法阶的上界

3. 乘法阶计算

• 在 $\phi(p)$ 的因子中寻找最小的 $\delta$ 使得 $b^\delta \equiv 1 \pmod{p}$
• 通过不断除以质因子来找到最小阶

4. 大数乘法取模

long long calc(long long A, long long B, long long P) {
    long long C = A * B - (long long)((long double)A * B / P + 0.1) * P;
    return C < 0 ? C + P : C;
}

使用浮点数技巧避免大数乘法溢出。

复杂度分析

• 质因数分解：$O(\sqrt{p})$，但只执行一次
• 单次查询：$O(\log^2 p)$，主要来自快速幂和阶的计算
• 总复杂度：$O(T \log^2 p)$，适合 $T \leq 10^5$ 的数据范围

算法标签

数论算法：

• 质因数分解
• 欧拉函数
• 乘法阶
• 快速幂

数学工具：

• 模运算
• 同余理论
• 群论基础

优化技术：

• 浮点数取模技巧
• 因子分解优化

总结

这道题通过深入分析题目背景，将复杂的算术判定问题转化为数论中的乘法阶计算问题。算法核心在于利用欧拉定理和阶的性质，高效地找到满足条件的最小 $k$。实现中需要注意大数运算的精度处理和边界情况判断。