@ysner
2018-10-03T15:05:39.000000Z
字数 1900
阅读 2210
BSGS
数论
好像还是模板题。
虽然说我不看标签还不一定能意识到要用bsgs
看到递推式之类的,应该要想到矩乘或者某些数学理论。。。
题目的问题矩乘处理不了。
也只能。
设第天读到第页。
想想怎么把未知数弄到指数那里去。
数学必修五中常常给出递推式,要我们证一个玩意儿是等比数列。
这里要反其道而行。
显然的时候需要特判。
我在特判上栽了两次。。。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e4,mod=45807;
int T;
int p,a,b,s,t,z,y;
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il ll ksm(re ll S,re ll n)
{
re ll T=S;S=1;
while(n)
{
if(n&1) S=S*T%p;
T=T*T%p;
n>>=1;
}
return S;
}
struct Hash_table
{
struct Edge{int u,v,nxt;}e[N*10];
int h[N],cnt;
il void clear(){memset(h,-1,sizeof(h));cnt=0;}
il void add(re int u,re int v,re int w){e[++cnt]=(Edge){w,v,h[u]};h[u]=cnt;}
il int Query(re int x)
{
for(re int i=h[x%mod];i+1;i=e[i].nxt)
if(e[i].u==x) return e[i].v;
return -1;
}
il void solve(re int y,re int z)
{
y%=p;z%=p;
if(!y||!z) {puts("-1");return;}
re int m=sqrt(p)+1;clear();
for(re int i=0,t=z;i<m;++i,t=1ll*t*y%p) add(t%mod,i,t);
for(re int i=1,tt=ksm(y,m),t=tt;i<=m;++i,t=1ll*tt*t%p)
{
re int j=Query(t);if(j==-1) continue;
printf("%d\n",i*m-j+1);return;
}
puts("-1");
}
}BSGS;
int main()
{
T=gi();
while(T--)
{
p=gi();a=gi();b=gi();s=gi();t=gi();
if(s==t) {puts("1");continue;}
if(a==0)
{
if(b==t) puts("2");else puts("-1");//if(b==t) puts("1");????
continue;
}
if(a==1)
{
if(b==0) puts("-1");
else
{
re ll gu=1ll*(t+p-s)%p*ksm(b,p-2)%p;
printf("%lld\n",gu+1);//printf("%lld\n",gu);????
}
continue;
}
re ll gu=1ll*b*ksm(a-1,p-2)%p;
y=a;z=1ll*(t+gu)%p*ksm(s+gu,p-2)%p;
BSGS.solve(y,z);
}
return 0;
}