题意：求$a^y \equiv b \pmod{p}$最小的$y$。（0<=x, y, p<=10^9）
#include#include #include #include #include typedef long long ll;using namespace std;int gcd(int a, int b) { return b?gcd(b, a%b):a; }void exgcd(ll a, ll b, ll &d, ll &x, ll &y) { if(!b) { d=a; x=1; y=0; return; } exgcd(b, a%b, d, y, x); y-=a/b*x; }int ni(int a, int b) { static ll x, y, d; exgcd(a, b, d, x, y); return (x+b)%b;}int ipow(int a, int b, int c) { int x=1; for(; b; b>>=1, a=(ll)a*a%c) if(b&1) x=(ll)x*a%c; return x; }struct H { static const int md=3999997; bool vis[md]; int dt[md], foo[md], s[md], top; void clr() { while(top) { int x=s[top--]; vis[x]=0, dt[x]=-1; } } void add(int a, int b) { int x=a%md; while(1) { if(!vis[x] || dt[x]==a) { if(!vis[x]) s[++top]=x; vis[x]=1; dt[x]=a; foo[x]=b; break; } ++x; if(x==md) x=0; } } int find(int a) { int x=a%md; while(1) { if(!vis[x]) return -1; if(dt[x]==a) return foo[x]; ++x; if(x==md) x=0; } }}h;int a, b, mo;bool spj() { if(b==1) puts("0"); else if(!a && !b) puts("1"); else if(!b) puts("No Solution"); else return 0; return 1;}void work() { b%=mo; if(spj()) return; for(int i=0, t=1; i<30; ++i, t=(ll)t*a%mo) if(t==b) { printf("%d\n", i); return; } int a1=0, d=1, g; while((g=gcd(a, mo))!=1) { if(b%g) { puts("No Solution"); return; } ++a1, mo/=g, b/=g, d=(ll)a/g*d%mo; } d=ni(d, mo); int m=sqrt(0.5+mo); h.clr(); for(int i=0, t=(ll)b*d%mo; i
拓展的大步小步= =
跪跪跪：http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4
由于$c$不一定是质数，因此不能用原来的bsgs算法
而这样的话有解但是可能不唯一。
但是还是容易想到枚举$i$解出这个方程$a^{im} x \equiv b \pmod{p}$ 然后查找$x$是否为$a^t$，然后答案就是$im+t$。
可是发现这样的解集大小为$(a^{im}, p)$，有可能很大= =无法承受....
我们来通过将方程变成一种等价形式来简化问题：
我们将式子同时除以$d=(a, p)$，得到：$\frac{a}{d} a^m \equiv \frac{b}{d} \pmod{\frac{p}{d}}$。（当然如果$b$不能整除$d$那么方程无解辣= =将$b = xxx$搞一下就可以知道辣= =）
一直进行了$t$次直到$(a, p_{t}) = 1$，令$D = a^t \frac{1}{\prod_{i=1}^{t} d_{t}}$，那么显然$(D, p_{t}) = 1$是不是辣= =
那么得到原方程的等价形式$a^h \equiv b_{t} D^{-1} \pmod{p_t}$，解出$h$那么原问题答案就是$h+t$辣= =
那么裸$bsgs$辣
可是这里要注意哦，可能存在$y<t$的情况哟，由于$t$松的上界为$log_2 p$，我们先枚举一下判断就行辣....