1 /************************************************************** 2     Problem: 3239 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:280 ms 7     Memory:2932 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cmath>12 #include <map>13  14 using namespace std;15 typedef long long ll;16  17 ll p, y, z, B;18 map <ll, int> mp;19  20 ll pow(ll a, ll x) {21   a %= p;22   ll res = 1, base = a;23   while (x) {24     if (x & 1) (res *= base) %= p;25     (base *= base) %= p;26     x >>= 1;27   }28   return res;29 }30  31 int main() {32   ll i, now, base, tmp;33   while (scanf("%lld%lld%lld", &p, &y, &z) != EOF) {34     mp.clear();35     y %= p;36     if (!y) {37       if (!z) puts("1");38       else puts("no solution");39       goto end_of_work;40     }41     B = (int) ceil(sqrt(p)), now = 1;42     mp[1] = B + 1;43     for (i = 1; i < B; ++i) {44       (now *= y) %= p;45       if (!mp[now]) mp[now] = i;46     }47     now = 1, base = pow(y, p - B - 1);48     for (i = 0; i < B; ++i) {49       tmp = mp[z * now % p];50       if (tmp) {51     if (tmp == B + 1) tmp = 0;52     printf("%lld\n", i * B + tmp);53     goto end_of_work;54       }55       (now *= base) %= p;56     }57     puts("no solution");58   end_of_work:;59   }60   return 0;61 }