BSGS问题
解题思路:
本题是要求高次同余方程的最小正整数解,是 $BSGS$ 算法的模板题。
C++ 代码
#include <iostream>
#include <cstring>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long LL;
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 (mod p) 的值
for(int i = 0, j = b % p; i < k; i++) //枚举所有 y,将所有可能的值存下来
{
hash[j] = i;
j = (LL)j * a % p;
}
int ak = 1; //记录 a^k
for(int i = 0; i < k; i++) ak = (LL)ak * a % p; //求 a^k
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 满足条件,说明找到最小正整数解,直接返回 k * x - y
j = (LL)j * ak % p; //继续往下枚举
}
return -1; //到此说明无解,返回 -1
}
int main()
{
int a, p, b;
while(scanf("%d%d%d", &a, &p, &b), a || p || b)
{
int res = bsgs(a, b, p);
if(res == -1) puts("No Solution");
else printf("%d\n", res);
}
return 0;
}