POJ 2417

题目大意

暂无

题目解法

暂无

RTFC

#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;
}