You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
67 lines
1.5 KiB
C++
67 lines
1.5 KiB
C++
#include <cmath>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
typedef long long i64;
|
|
void exgcd(i64 a, i64 b, i64 &x, i64 &y)
|
|
{
|
|
b == 0 ? (x = 1, y = 0) : (exgcd(b, a % b, y, x), y -= (a / b) * x);
|
|
}
|
|
struct HashTable
|
|
{
|
|
static const size_t sz = 500009;
|
|
i64 idx[sz], val[sz];
|
|
void init()
|
|
{
|
|
memset(idx, -1, sizeof(idx));
|
|
memset(val, -1, sizeof(val));
|
|
}
|
|
void insert(i64 i, i64 v)
|
|
{
|
|
i64 j = i % sz;
|
|
while (idx[j] != -1 && idx[j] != i)
|
|
{
|
|
j++;
|
|
if (j == sz)
|
|
j = 0;
|
|
}
|
|
if (val[j] == -1)
|
|
{
|
|
idx[j] = i;
|
|
val[j] = v;
|
|
}
|
|
}
|
|
i64 find(i64 i)
|
|
{
|
|
i64 j = i % sz;
|
|
while (idx[j] != -1 && idx[j] != i)
|
|
{
|
|
j++;
|
|
if (j == sz)
|
|
j = 0;
|
|
}
|
|
return val[j];
|
|
}
|
|
} H;
|
|
int main()
|
|
{
|
|
for (i64 a, b, c; ~scanf("%lld%lld%lld", &c, &a, &b) && a | b | c;)
|
|
{
|
|
H.init();
|
|
i64 m = i64(ceil(sqrt(c))), d = 1;
|
|
for (int i = 0; i < m; i++, d = d * a % c)
|
|
H.insert(d, i);
|
|
i64 res = 1, x, y;
|
|
bool flag = false;
|
|
for (i64 i = 0; i < m && !flag; i++, res = res * d % c)
|
|
{
|
|
exgcd(res, c, x, y);
|
|
x = (x * b % c + c) % c;
|
|
i64 j = H.find(x);
|
|
if (j != -1)
|
|
printf("%lld\n", i * m + j), flag = true;
|
|
}
|
|
if (!flag)
|
|
puts("no solution");
|
|
}
|
|
return 0;
|
|
} |