从这里开始
离散对数和BSGS算法
设$x$是最小的非负整数使得$a^{x}\equiv b\ \ \ \pmod{m}$，则$x$是$b$以$a$为底的离散对数，记为$x = ind_{a}b$。
假如给定$a, b, m$，考虑如何求$x$，或者输出无解，先考虑$(a, m) = 1$的情况。
定理1（欧拉定理） 若$(a, m) = 1$，则$a^{\varphi(m)}\equiv 1 \pmod{m}$。
证明这里就不给出，因为在百度上随便搜一搜就能找到。
不过，这个定理告诉我们，在$(a, m) = 1$的情况下，若存在答案，则答案不会超过$\varphi(m) - 1$。
考虑$a^{x} \equiv b \pmod{m}$，通过一些操作可以得到：
$a^{x - k} \equiv a^{-k}b \pmod{m}$
因此可以选取正整数$c$，将$x$表示为$ic + j$的形式，然后有：
$a^{ic} \equiv a^{-j}b \pmod{m}$
考虑预处理$a^{-j}b$，以它的值为键，最小的$j$为值存入Hash表或者Map中。
这样有什么用呢？你可以快速枚举$a^{ic}$，然后你将这个值在Hash表中查一查对应的最小的$j$，如果查到就可以得到答案了。
Code
/**
* poj
* Problem#2417
* Accepted
* Time: 16ms
* Memory: 1372l
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef bool boolean; int p, x, a; typedef class HashMap {
private:
static const int M = ;
public:
int ce;
int h[M], key[M], val[M], next[M]; HashMap():ce(-) { } void insert(int k, int v) {
int ha = k % M;
for (int i = h[ha]; ~i; i = next[i])
if (key[i] == k) {
val[i] = v;
return;
}
++ce, key[ce] = k, val[ce] = v, next[ce] = h[ha];
h[ha] = ce;
} int operator [] (int k) {
int ha = k % M;
for (int i = h[ha]; ~i; i = next[i])
if (key[i] == k)
return val[i];
return -;
} void clear() {
ce = -;
memset(h, -, sizeof(h));
}
}HashMap; int qpow(int a, int pos) {
int pa = a, rt = ;
for (; pos; pos >>= , pa = pa * 1ll * pa % p)
if (pos & )
rt = rt * 1ll * pa % p;
return rt;
} void exgcd(int a, int b, int& d, int &x, int &y) {
if (!b)
d = a, x = , y = ;
else {
exgcd(b, a % b, d, y, x);
y -= (a / b) * x;
}
} int inv(int a, int n) {
int d, x, y;
exgcd(a, n, d, x, y);
return (x < ) ? (x + n) : (x);
} inline boolean init() {
return ~scanf("%d%d%d", &p, &x, &a);
} int cs;
HashMap mp;
inline int ind() {
mp.clear();
cs = sqrt(p - + 0.5);
if (cs == ) cs++;
int ainv = inv(x, p), iap = a * 1ll * qpow(ainv, cs - ) % p;
for (int i = cs - ; ~i; i--, iap = iap * 1ll * x % p)
mp.insert(iap, i);
int cp = qpow(x, cs), pw = ;
for (int i = ; i < p; i += cs, pw = pw * 1ll * cp % p)
if (~mp[pw])
return mp[pw] + i;
return -;
} inline void solve() {
int res = ind();
if (res == -)
puts("no solution");
else
printf("%d\n", res);
} int main() {
while (init())
solve();
return ;
}
BSGS
扩展BSGS算法
使刚刚的问题更一般，去掉$(a, m) = 1$的条件。
此时逆元不一定存在，所以不能用上述的BSGS算法来做。
考虑去掉它们的公约数$d$。
得到
$a^{x - 1}\cdot\frac{a}{d} \equiv \frac{b}{d} \pmod{\frac{m}{d}}$
在这步中，如果$b \nmid d$，那么显然无解。
否则我可以令$x' = x - 1,k' = \frac{a}{d}, b'=\frac{b}{d}, m' = \frac{m}{d}$进行换元得到：
$k'a^{x'} \equiv b' \pmod{m'}$
如果$(a, m') = 1$，那么直接BSGS解这个方程，然后带回去算原先的$x$，否则可以继续计算$a$和$m'$的最大公约数，继续除掉它，直到$(a, m) = 1$，然后BSGS解方程。
因为最大公约数不为1，每次至少除以2，1和任何数互质，因此总共除的次数不会超过$\log_{2}m$。
但是这么做存在一个问题，假如除的次数为$k$，那么它会忽略大于等于0小于$k$的解，因此，除的时候判一下即可。
Code
/**
* poj
* Problem#3243
* Accepted
* Time: 47ms
* Memory: 1248k
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean; int x, a, m; typedef class HashMap {
private:
static const int M = ;
public:
int ce;
int h[M], key[M], val[M], next[M]; HashMap():ce(-) { } void insert(int k, int v) {
int ha = k % M;
for (int i = h[ha]; ~i; i = next[i])
if (key[i] == k) {
val[i] = v;
return;
}
++ce, key[ce] = k, val[ce] = v, next[ce] = h[ha];
h[ha] = ce;
} int operator [] (int k) {
int ha = k % M;
for (int i = h[ha]; ~i; i = next[i])
if (key[i] == k)
return val[i];
return -;
} void clear() {
ce = -;
memset(h, -, sizeof(h));
}
}HashMap; int qpow(int a, int pos, int m) {
int pa = a, rt = ;
for (; pos; pos >>= , pa = pa * 1ll * pa % m)
if (pos & )
rt = rt * 1ll * pa % m;
return rt;
} int gcd (int a, int b) {
return (b) ? (gcd(b, a % b)) : (a);
} void exgcd(int a, int b, int& d, int &x, int &y) {
if (!b)
d = a, x = , y = ;
else {
exgcd(b, a % b, d, y, x);
y -= (a / b) * x;
}
} int inv(int a, int n) {
int d, x, y;
exgcd(a, n, d, x, y);
return (x < ) ? (x + n) : (x);
} inline boolean init() {
return ~scanf("%d%d%d", &x, &m, &a) && (x || m || a);
} int cs;
HashMap mp;
inline int ind(int pro, int x, int a, int p) {
mp.clear();
cs = sqrt(p - + 0.5);
int ainv = inv(x, p), iap = a * 1ll * qpow(ainv, cs - , p) % p;
for (int i = cs - ; ~i; i--, iap = iap * 1ll * x % p)
mp.insert(iap, i);
int cp = qpow(x, cs, p), pw = pro;
for (int i = ; i < p; i += cs, pw = pw * 1ll * cp % p)
if (~mp[pw])
return mp[pw] + i;
return -;
} int exind(int x, int a, int m) {
if (a == ) return ;
int d, k = , pro = ;
while ((d = gcd(x, m)) != ) {
if (a % d) return -;
if (pro == a) return k;
a /= d, m /= d, pro = (pro * 1ll * (x / d)) % m, k++;
}
int rt = ind(pro, x % m, a, m);
return (~rt) ? (rt + k) : (-);
} inline void solve() {
int res = exind(x % m, a % m, m);
if (res == -)
puts("No Solution");
else
printf("%d\n", res);
} int main() {
while (init())
solve();
return ;
}
ex-BSGS