考虑一个问题:A^x%p=B,给定A,B,p，求x的最小非负整数解。
在p是质数的情况下，这个问题比較简单。
A^x=B(mod P) (P is a Prime, A,B<P) Let m = floor(sqrt(P)) Put A^0,A^1,...A^(m-1) into HashSet(You Can Also Use Map in STL),for Example M[A^i]=i.
if A^i=A^j(i<j), M[A^i=A^j]=i.
Enumerate i, Let x=i*m+j, A^(i*m)*A^j=B(mod C) Let E=A^(i*m),F=A^j,E*F=B(mod P) because (E,C)=1,(E,C)|B,we can use EXTgcd to get F.
If F is in the HashSet,then the minimum answer x=i*m+M[F].
Because P is a Prime, and A,B<P, then A^(P-1)=1(mod P). Then if a answer exists, the minimum answer must less then P.
So the range of i is [0,P/m].
If for all i we cannot find a answer, then no solution.
我亲手胡乱写的东西，能看懂才怪！
再附上代码吧：（我的小数据范围是暴力的）
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
inline void Exgcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (!b) { d = a, x = 1, y = 0; }
else { Exgcd(b, a % b, d, y, x), y -= x * (a / b); }
}
inline LL gcd(LL a, LL b) {
return (!b) ? a : gcd(b, a % b);
}
inline LL Solve(LL a, LL b, LL c) { // ax=b(mod c)
LL d, x, y;
Exgcd(a, c, d, x, y);
return (x + c) % c * b % c;
}
LL ksm(LL x, LL y, LL p) {
LL res = 1, t = x;
for(; y; y >>= 1) {
if (y & 1) res = res * t % p;
t = t * t % p;
}
return res;
}
const int mod = 13131;
struct Hashset {
int head[mod], next[40010], f[40010], v[40010], ind;
void reset() {
ind = 0;
memset(head, -1, sizeof head);
}
void insert(int x, int _v) {
int ins = x % mod;
for(int j = head[ins]; j != -1; j = next[j])
if (f[j] == x) {
v[j] = min(v[j], _v);
return;
}
f[ind] = x, v[ind] = _v;
next[ind] = head[ins], head[ins] = ind++;
}
int operator [] (const int &x) const {
int ins = x % mod;
for(int j = head[ins]; j != -1; j = next[j])
if (f[j] == x)
return v[j];
return -1;
}
}S;
int main() {
LL A, B, C;
LL i;
while(scanf("%I64d%I64d%I64d", &C, &A, &B) == 3) {
if (C <= 100) {
LL d = 1;
bool find = 0;
for(i = 0; i < C; ++i) {
if (d == B) {
find = 1;
printf("%I64d
", i);
break;
}
d = d * A % C;
}
if (!find)
puts("no solution");
}
else {
int m = (int)sqrt(C);
S.reset();
LL d = 1;
for(i = 0; i < m; ++i) {
S.insert(d, i);
d = d * A % C;
}
bool find = 0;
int ins;
for(i = 0; i * m < C; ++i) {
LL t = Solve(ksm(A, i * m, C), B, C);
if ((ins = S[t]) != -1) {
printf("%I64d
", i * m + ins);
find = 1;
break;
}
}
if (!find)
puts("no solution");
}
}
return 0;
}