@ysner
2018-10-03T10:54:33.000000Z
字数 2600
阅读 2154
总结
数论
BSGS
一种用来求解高次同余方程的算法。
一般问题形式:求使得的最小非负。
要求是质数。
由费马小定理可知,,所以暴力枚举只要枚举到即可。
但是由于一般都很大,所以一般都跑不动。。。
优化算法
现在令(其中)。
则方程可化为,
然后可以发现(否则就是负数)
所以我们可以暴力枚举,与所得的存在哈希表里,然后再暴力枚举,最后得出结果。
还要注意一些边界:
struct Hash_Table
{
int h[N],cnt;
struct Edge{int u,v,nxt;}e[N*10];
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)
{
re int t=x%mod;
for(re int i=h[t];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,re int p)
{
y%=p;z%=p;
if(!y) {puts("no solution");return;}
if(z==1) {puts("0");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,p),t=tt;i<=m+1;++i,t=1ll*t*tt%p)
{
re int j=Query(t);if(j==-1) continue;
printf("%d\n",i*m-j);return;
}
puts("no solution");
}
}BSGS;
int main()
{
re int y,p,z;
while(scanf("%d%d%d",&p,&y,&z)!=EOF)
{
BSGS.solve(y,z,p);
}
return 0;
}
不要求是质数。
那就说明很可能,不满足费马小定理。
费马小定理提供了枚举上限,没有它这种问题就不好做了。。。
想想怎么把约分。
令。
把方程改写成等式形式:
最后形式为(那个反正是个正整数)
注意边界:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define il inline
#define re register
#define ll long long
#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;
il ll ksm(re ll S,re ll n,re int p)
{
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
{
int h[N],cnt;
struct Edge{int u,v,nxt;}e[N*10];
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)
{
re int t=x%mod;
for(re int i=h[t];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,re int p)
{
if(z==1) {puts("0");return;}
re int k=0,a=1;
while(233)
{
re int t=__gcd(y,p);if(t==1) break;
if(z%t) {puts("No Solution");return;}
z/=t;p/=t;++k;a=1ll*a*y/t%p;
if(z==a) {printf("%d\n",k);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,p),t=1ll*a*tt%p;i<=m+1;++i,t=1ll*t*tt%p)
{
re int j=Query(t);if(j==-1) continue;
printf("%d\n",i*m-j+k);return;
}
puts("No Solution");
}
}BSGS;
int main()
{
re int y,p,z;
while(scanf("%d%d%d",&y,&p,&z))
{
if(!p&&!y&&!z) break;
BSGS.solve(y,z,p);
}
return 0;
}