扩展BSGS
Orz zyf……然而他的题解对AC大神的题解作了引用……而坑爹的百度云……呵呵了。。。
扩展BSGS模板题
/**************************************************************
Problem: 2480
User: Tunix
Language: C++
Result: Accepted
Time:6948 ms
Memory:2212 kb
****************************************************************/ //BZOJ 2480
#include<cstdio>
#include<cmath>
#include<map>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
inline int getint(){
int r=,v=; char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if (ch=='-') r=-;
for(; isdigit(ch);ch=getchar()) v=v*-''+ch;
return r*v;
}
const int N=;
/*******************template********************/ int a,p,b; inline int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
LL Pow(LL a,LL b,LL P){
LL r=;
for(;b;b>>=,a=a*a%P) if (b&) r=r*a%P;
return r;
}
map<int,int>mp;
int ex_BSGS(int a,int p,int b){
int d=,res=,cnt=;
LL t=;
a%=p; b%=p;
for(int i=,j=;i<=;i++,j=(LL)j*a%p) if (j==b) return i;
t=%p; while((d=gcd(a,p))!=){
if (b%d) return -;
p/=d; b/=d; t=t*a/d%p;
++cnt;
}
mp.clear();
int m=ceil(sqrt(p));
for(int i=,j=;i<m;i++,j=(LL)j*a%p) mp[(LL)b*j%p]=i;
a=Pow(a,m,p);
for(int i=,j=t;i<=m;i++,j=(LL)j*a%p)
if (i && mp.count(j))
return i*m-mp[j]+cnt;
return -;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("2480.in","r",stdin);
freopen("2480.out","w",stdout);
#endif
int ans;
while(scanf("%d%d%d",&a,&p,&b)!=EOF && a && p && b){
ans=ex_BSGS(a,p,b);
if (ans>=) printf("%d\n",ans);
else puts("No Solution");
}
return ;
}
2480: Spoj3105 Mod
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 248 Solved: 103
[Submit][Status][Discuss]
Description
已知数a,p,b，求满足a^x≡b(mod p)的最小自然数x。
Input
每个测试文件中最多包含100组测试数据。
每组数据中，每行包含3个正整数a,p,b。
当a=p=b=0时，表示测试数据读入完全。
Output
对于每组数据，输出一行。
如果无解，输出“No Solution”（不含引号），否则输出最小自然数解。
Sample Input
5 58 33
2 4 3
0 0 0
2 4 3
0 0 0
Sample Output
9
No Solution
No Solution
HINT
10%的数据，a,p,b≤10000；
对于另外30%的数据，p为质数；
100%的数据，a,p,b≤1e9。