BSGS对于高阶同余方程的求解
通过题目给出的式子
\(x_{2} \equiv a*x_{1} \mod p\)
\(x_{2}+\frac{b}{a} \equiv a*x_{1}+\frac{b}{a} \mod p\)
\(x_{3}=a*x_{2}+b \equiv (a^2)*x_{1}+a*b+b]\mod p\)
\(对该式子进行继续推导可以得出\)
\(x_{i}=a^{i-1}*x1+\sum_{j=0}^{i-2}a^{j} \mod p\)
\(化简得t \equiv a^{i-1}x_1+\frac{b}{1-a}-\frac{b}{1-a}a^{i-1} \mod p\)
\(继续化简得到 a^{i-1}\equiv \frac{t-\frac{b}{1-a}]}{x_1-\frac{b}{1-a}} \mod p\)
\(接下来我们进行分类讨论\)
1
\(当x_1=t时，直接输出1\)
2
\(当a=0时，x_i=b\)
3
\(当a=1时，有x_i\equiv x_1+b(i-1)\mod p\)
\(这时候我们就要面对高次同余方程\)
\(对于高次同余方程我们一般通过BSGS求解\)
\(接下来讲解BSGS\)
\(由扩展欧拉定理我们可以知道a^{x} \equiv a^{x \mod p} \mod p\)
\(可知其\mod p情况下的最小循环节为f(p)\)
\(因为f(p)<p ,所以考虑x \in [0,p]\)
\(如果暴力枚举,时间为O(p)\)
\(很显然我们无法接受\)
\(令x=im-j,其中m=\lceil \sqrt p \rceil,j \in [0,m-1]\)
\(a^{im-j}\equiv b\mod p\)
\(化简得a^{mi}\equiv ba^{j}\mod p\)
\(先枚举j,把(ba^{j},j)存入哈希表，如果key重复，用更大的j替代\)
\(再枚举i，计算a^{mi}当找到第一个相同的key 那么就找到了最小的 x=im-j\)
\(code:\)
点击查看代码
plaintext
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
int qpw(int a,int b,int mod){
int ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
int inv(int x,int mod){
return qpw(x,mod-2,mod);
}
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int bsgs(int a,int b,int mod){
a%=mod,b%=mod;
unordered_map<int,int>mp;
int m=ceil(sqrt(mod)),t=b;
mp[b]=0;
for(int j=1;j<m;j++){
t=t*a%mod;
mp[t]=j;
}
int mi=1;
for(int i=1;i<=m;i++){
mi=mi*a%mod;
}
t=1;
for(int i=1;i<=m;i++){
t=t*mi%mod;
if(mp.count(t)){
return i*m-mp[t];
}
}
return -1;
}
void solve() {
int p,a,b,x,t;
cin>>p>>a>>b>>x>>t;
if(x==t)cout<<1<<'\n';
else if(a==1){
t=((t-x)%p+p)%p;
if(t%gcd(b,p)){
cout<<-1<<'\n';
}else {
if((t*inv(b,p)+1)%p==0){
cout<<p<<'\n';
}else {
cout<<(t*inv(b,p)+1)%p<<'\n';
}
}
}else if(a==0){
if(b==t){
cout<<2<<'\n';
}else {
cout<<-1<<'\n';
}
}else {
long long ans = bsgs(a, ((t - b * inv(1 - a, p)) % p + p) % p * inv(((x - b * inv(1 - a, p)) % p + p) % p, p), p) % p;
if(ans==-1){
cout<<-1<<'\n';
}else cout<<ans+1<<'\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int _=1;
cin>>_;
while(_--)solve();
}