poj2417 bsgs算法非逆元模板，用于求解A^x=B(mod C)的方程

参考博客 https://blog.csdn.net/clover_hxy/article/details/50683832
关于欧拉定理推论的证明 https://www.cnblogs.com/aseer/p/9675610.html/*
给定A,B,C,C是质数，求出A^x=B(mod C)的解
解：A^x = A^(x % phi[C]) = B(mod C) (欧拉定理推论)
x % phi[C] < C
所以不超过C的范围内必有一个解，
只要求到C即可，
进行分块，另 m=sqrt(C),向上取整,那么 x=i*m-j
原式==》A^j*B = A^(m*i)(mod C)
先枚举j，将A^j*B进行hash
再枚举i，从hash表中找到第一个满足条件的A^j*B
此时x=i*m-j
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
#define ll long long
ll a,b,c,m,f[];
map<ll,int>mp;
ll Pow(ll x){
ll res=,aa=a;
while(x>){
if(x%)
res=res*aa%c;
x>>=;
aa=aa*aa%c;
}
return res;
}
int main(){
while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF){
mp.clear();
if(a%c==){//c|a,显然是不存在解x的，除非
puts("no solution");
continue;
}
int p=;
m=ceil(sqrt(c*1.0));
ll ans; for(int j=;j<=m;j++){//预处理所有j的情况，建立hash表
if(j==){
ans=b%c;mp[ans]=j;continue;
}
ans=(ans*a)%c;
mp[ans]=j;
} ll t=Pow(m);
ans=;
for(int i=;i<=m;i++){
ans=(ans*t)%c;
if(mp[ans]){//枚举每个块ans=a^(m*i)=a^j*b,把hash表中的那个j找到即可
int t=i*m-mp[ans];
printf("%d\n",(t%c+c)%c);
p=;
break;
}
}
if(!p)
puts("no solution");
}
}