🧠 题解（Solution）

✅ 本质分析

这是一个典型的离散对数问题：

给定素数 $P$，底数 $B$，模 $P$ 下的目标值 $N$，求最小的 $L$ 满足：

𝐵𝐿≡𝑁(mod𝑃)B L ≡N(modP) 这与常规对数类似，但是在模运算意义下进行的，求解方法不同于普通实数运算。

✅ 解法：Baby-Step Giant-Step 算法（BSGS）

由于直接枚举 $L$ 的复杂度是 $O(P)$，对于 $P$ 接近 $2^{31}$ 的情况完全不可行。

我们可以使用 Baby-Step Giant-Step 算法（BSGS），它是求解离散对数的经典算法，其时间复杂度为：

𝑂(𝑃⋅log⁡𝑃) ✅ 算法核心步骤

设 $m = \lceil \sqrt{P} \rceil$；

预处理所有：

baby step:𝐵𝑗 mod𝑃 for 𝑗=0,1,…,𝑚−1

存入哈希表（key 是值，value 是指数 $j$）；

计算：

𝐵−𝑚 mod𝑃=(𝐵𝑚)−1 mod𝑃 使用费马小定理求逆元；

对于每个 $i = 0$ 到 $m$，计算：

𝑦=𝑁⋅(𝐵−𝑚)𝑖 mod𝑃

如果 $y$ 在哈希表中出现，则 $L = i \cdot m + j$ 为答案；

若遍历完没有匹配项，则输出 no solution。

✅ 补充数学背景 根据费马小定理，对于素数 $P$ 和 $B \not\equiv 0 \pmod{P}$：

𝐵 𝑃 − 1 ≡ 1 ( m o d 𝑃 ) B P−1 ≡1(modP) 从而：

𝐵 − 1 ≡ 𝐵 𝑃 − 2 ( m o d 𝑃 ) B −1 ≡B P−2 (modP) 这在计算模逆元时会用到。

✅ 输出要求 若存在多个解，输出最小的 $L$；

若无解，输出 no solution；

每行一个结果，对应一组输入。 代码实现

#include <map>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int a,p,c;
ll qpow(ll a,ll x)
{
    ll res = 1;
    while(x){
        if(x&1) res = res * a % p;
        a = a * a % p;
        x >>= 1;
    }
    return res%p;
}
int BsGs()
{
    map<ll,int> mp;
    int k = sqrt(p*1.0) + 0.5;
    ll v = c;
    for(int j = 1; j <= k ; ++j){
       v =  v * a % p;
       mp[v] = j;
    }
    v = qpow(a,k);
    ll vv = 1;
    for(int i = 1; i <= k; ++i){
         vv = vv * v % p;
         if(mp[vv]) return i * k - mp[vv];
    }
    return -1;
}
int main()
{
    while(cin>>p>>a>>c)
    {
        int ans = BsGs();
        if(ans == -1) cout<<"no solution"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}