A^x = B (mod C) 的模板题，不够要用扩展BSGS
（虽然AC，但完全理解不了模板0.0，以后学好数学在来慢慢理解555555）
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>
const int MAXN = + ;
const int maxn = ;
const int INF = 0x7fffffff;
using namespace std;
typedef long long ll;
struct Hash{
ll a,b,next;
}Hash[maxn << ];
ll flg[maxn + ];
ll top,idx;
void ins(ll a,ll b){
ll k = b & maxn;
if (flg[k] != idx){
flg[k] = idx;
Hash[k].next = -;
Hash[k].a = a;
Hash[k].b = b;
return ;
}
while (Hash[k].next != -){
if(Hash[k].b == b) return ;
k = Hash[k].next;
}
Hash[k].next = ++ top;
Hash[top].next = -;
Hash[top].a = a;
Hash[top].b = b;
}
ll Find(ll b){
ll k = b & maxn;
if (flg[k] != idx) return -;
while (k != -){
if(Hash[k].b == b) return Hash[k].a;
k = Hash[k].next;
}
return -;
}
ll gcd(ll a,ll b) {return b == ? a: gcd(b, a % b);}
ll exgcd(ll a, ll b, ll &x, ll &y){
if (b == ){x = ; y = ; return a;}
ll tmp = exgcd(b, a % b, y, x);
y -= x * (a / b);
return tmp;
}
ll solve(ll a, ll b, ll c){
ll x, y, Ans;
ll tmp = exgcd(a, c, x, y);
Ans = (ll)(x * b) % c;
return Ans >= ? Ans : Ans + c;
}
ll pow(ll a, ll b, ll c){
ll ret = ;
while(b)
{
if(b & ) ret = ret * a % c;
a = a*a%c;
b>>= ;
}
return ret;
}
ll BSGS(ll A, ll B, ll C){
top = maxn;
++idx;
ll buf = % C, D = buf, K, tmp;
for (ll i = ; i <= ; i++){
if (buf == B) return i;
buf = (buf * A) % C;
}
ll d = ;
while ((tmp = gcd(A, C)) != ){
if (B % tmp != ) return -;
d++;
B /= tmp;
C /= tmp;
D = D * A / tmp % C;
}
//hash表记录1-sqrt(c)的值
ll M = (ll)ceil(sqrt(C * 1.0));
buf = % C;
for (ll i = ; i <= M; i++){
ins(i, buf);
buf = (buf * A) % C;
}
K = pow(A, M, C);
for (ll i = ; i <= M; i++){
tmp = solve(D, B, C);
ll w;
if (tmp >= && (w = Find(tmp)) != -) return i * M + w + d;
D = (D * K) % C;
}
return -;
} int main(){ ll A, B, C;
while (cin >> A >> C >> B && (A || B || C)){
B %= C;
ll tmp = BSGS(A, B, C); // A^x = B (mod C);
if (tmp >= ) cout << tmp << endl;
else cout << "No Solution\n";
}
return ;
}