扩展BSGS问题

解题思路：

本题是要求高次同余方程的最小正整数解，并且 $a$ 和 $p$ 不一定互质，因此这就是扩展 $BSGS$ 算法的模板题。

关于BSGS算法可参考

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <unordered_map>

using namespace std;

typedef long long LL;

const int INF = 1e8;

int exgcd(int a, int b, int &x, int &y) //扩展欧几里得算法
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int bsgs(int a, int b, int p) //BSGS 算法
{
    if(1 % p == b % p) return 0; //特判 0
    int k = sqrt(p) + 1;
    unordered_map<int, int> hash; //存储所有 b * a^y 的值
    for(int i = 0, j = b % p; i < k; i++) //i 表示 y，j 表示 b * a^y
    {
        hash[j] = i; //记录所有 b * a^y 对应的 y（y 尽可能大）
        j = (LL)j * a % p;
    }

    int ak = 1; //记录 a^k
    for(int i = 0; i < k; i++) ak = (LL)ak * a % p;

    for(int i = 1, j = ak; i <= k; i++) //i 表示 x，j 表示 ak^x
    {
        if(hash.count(j)) return (LL)k * i - hash[j]; //如果找到一组 x, y 满足方程，说明有解
        j = (LL)j * ak % p;
    }
    return -INF; //否则说明无解
}

int exbsgs(int a, int b, int p) //扩展 BSGS 算法
{
    b = (b % p + p) % p; //保证 b 是非负数
    if(1 % p == b % p) return 0; //特判 0
    int x, y;
    int d = exgcd(a, p, x, y); //求 a 和 p 的最大公约数
    if(d > 1) //如果 a 和 p 不互质，则需要处理
    {
        if(b % d) return -INF; //如果 b 不能整除 d，说明无解
        exgcd(a / d, p / d, x, y); //线性同余方程求 a / d 的逆元 x
        return exbsgs(a, (LL)b / d * x % (p / d), p / d) + 1; //递归处理
    }
    return bsgs(a, b, p); //如果 a 和 p 互质，直接用普通 BSGS 求
}

int main()
{
    int a, p, b;
    while(scanf("%d%d%d", &a, &p, &b), a || p || b)
    {
        int res = exbsgs(a, b, p);
        if(res < 0) puts("No Solution");
        else printf("%d\n", res);
    }
    return 0;
}