标題效果：給定一列數X(i+1)=(a*Xi+b)%p 最低要求i>0。是以Xi=t
0.0 這個問題可以1A那很棒
首先讨論特殊情況
如果X1=t ans=1
如果a=0 ans=b==t?
2:-1
若a=1 X1+b*(ans-1)==t (%p) 擴充歐幾裡得
令
temp=b/(a-1)
則有
(X(i+1)+temp)=a*(Xi+temp)
Xans=(X1+temp)*a^(ans-1)-temp
當中Xans%p=t
則有
(X1+temp)*a^(ans-1)-temp == t (%p)
兩側同乘a-1得
(a*X1-X1+b)*a^(ans-1) == (a-1)*t+b (%p)
令
Y=a*X1-X1+b
Z=a*t-t+b
Y*a^(ans-1) == Z(%p)
将Y和p約分
若Z%gcd(Y,p)!=0 return -1
令
A=a
B=Z*Y^-1
C=p
x=ans-1
A^x==B(%C)
然後就是EXBSGS的模闆了0.0 這個模闆我再也不想打第二遍了0.0
代碼沒法看了，諸位了解算法思想就好了0.0
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1001001
using namespace std;
typedef long long ll;
typedef pair<ll,ll> abcd;
ll X,Y,Z,a,b,c,p,t,A,B,C,D;
ll hash_table[M],val[M],tim[M],tot;
int Hash(ll x)
{
int pos=x%M;
while(1)
{
if(tim[pos]!=tot)
tim[pos]=tot,hash_table[pos]=-1,val[pos]=0x3f3f3f3f;
if(hash_table[pos]==-1||hash_table[pos]==x)
return hash_table[pos]=x,pos;
else
++pos,pos%=M;
}
}
int Get_Hash(ll x)
{
int pos=x%M;
while(1)
{
if(tim[pos]!=tot)
tim[pos]=tot,hash_table[pos]=-1;
if(hash_table[pos]==-1)
return -1;
if(hash_table[pos]==x)
return pos;
else
++pos,pos%=M;
}
}
ll GCD(ll x,ll y)
{
return y?GCD(y,x%y):x;
}
abcd EXGCD(ll x,ll y)
{
if(!y) return abcd(1,0);
abcd temp=EXGCD(y,x%y);
return abcd(temp.second,temp.first-x/y*temp.second);
}
ll Inverse(ll x)
{
ll temp=EXGCD(x,C).first;
return (temp%C+C)%C;
}
ll Extended_Big_Step_Giant_Step()
{
ll i,m,cnt=0,temp,base=1;
int pos;
if(B>=C)
return -1;
for(i=0,temp=1%C;i<=50;i++,temp*=A,temp%=C)
if(temp==B)
return i;
D=1;
while(temp=GCD(A,C),temp!=1)
{
if(B%temp)
return -1;
++cnt;
B/=temp;
C/=temp;
D*=A/temp;
D%=C;
}
B*=Inverse(D);B%=C;
m=(ll)ceil(sqrt(C)+1e-5);
++tot;
for(i=0,temp=1%C;i<m;i++,temp*=A,temp%=C)
pos=Hash(temp),val[pos]=min(val[pos],i);
for(i=1,base=1%C;i<=m;i++,base*=A,base%=C);
for(i=0,D=1%C;i<m;i++,D*=base,D%=C)
{
temp=EXGCD(D,C).first*B;
temp=(temp%C+C)%C;
pos=Get_Hash(temp);
if(~pos)
return i*m+val[pos]+cnt;
}
return -1;
}
ll Deal()
{
ll temp;
cin>>p>>a>>b>>X>>t;
if(X==t) return 1;
if(!a) return b==t?
2:-1; if(a==1) { t+=p-X;t%=p; //b*(ans-1)==t (%p) temp=GCD(b,p); if(t%temp) return -1; b/=temp;t/=temp;p/=temp; temp=(EXGCD(b,p).first*t%p+p)%p; return temp+1; } Y=(a*X-X+b)%p; Z=(a*t-t+b)%p; temp=GCD(Y,p); if(Z%temp) return -1; Y/=temp;Z/=temp;p/=temp; C=p; B=Z*Inverse(Y)%p; A=a; temp=Extended_Big_Step_Giant_Step(); if(temp==-1) return -1; return temp+1; } int main() { int T; for(cin>>T;T;T--) cout<<Deal()<<endl; }
版權聲明：本文部落格原創文章，部落格，未經同意，不得轉載。
本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/4681224.html，如需轉載請自行聯系原作者