注意 if (b == 1 || p == 1) return printf("0\n"), void(); 特判。
ExBSGS 相关笔记。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int exgcd(int a, int b, int &x, int &y) {
    if (!b) { x = 1, y = 0; return a; }
    int g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}
int inv(int n, int m) { int x, y, g = exgcd(n, m, x, y); return (x % m + m) % m; }

unordered_map<int, int> mp;
int BSGS(int a, int b, int p) {    // a^x = b (mod p)
    int T = sqrt(p) + 1; mp.clear();
    int mul = 1, now = 1;
    for (int i = 0; i <= T; i++) {
        if (mul == b) return i;
        if (!mp.count(b * mul % p)) mp[b * mul % p] = i;
        if (i < T) mul = mul * a % p;
    }
    for (int j = 1; j <= T; j++) {
        now = now * mul % p;
        if (mp.count(now)) return j * T - mp[now];
    }
    return -1;
}

int a, b, p;
void ExBSGS(int a, int b, int p) {
    if (b == 1 || p == 1) return printf("0\n"), void(); // ……?
    int k = 0;  //除了多少次
    int G = 1;
    while (1) {
        int g = gcd(a, p);
        if (g == 1) break;
        if (b % g) return puts("No Solution"), void();
        ++k, p /= g, b /= g, G = (G * a / g) % p;
        if (b == G) return printf("%lld\n", k), void(); // a^(x-k) = 1 (mod p), x-k = 0
    }
    int mul = 1;
    for (int i = 0; i <= k; i++) {  //指数 <= k 的情况
        if (mul == ::b) return printf("%lld\n", i), void();
        mul = mul * ::a % ::p;
    }
    G = inv(G, p);
    int ans = BSGS(a, b * G % p, p);
    if (~ans) printf("%lld\n", ans + k);
    else puts("No Solution");
}

signed main() {
    while (1) {
        scanf("%d%d%d", &a, &p, &b);
        if (!a && !b && !p) return 0;
        ExBSGS(a % p, b % p, p);
    }
    return 0;
}