R-L: 1248  naive: 4524 ms  discrete log: 1288 ms  ok
R-L: 1437  naive: 3992 ms  discrete log: 1492 ms  ok
R-L: 1593  naive: 3544 ms  discrete log: 1662 ms  ok
R-L: 2126  naive: 2763 ms  discrete log: 2256 ms  ok
R-L: 2459  naive: 2363 ms  discrete log: 2587 ms  ok
R-L: 2834  naive: 1985 ms  discrete log: 2990 ms  ok
R-L: 2853  naive: 2006 ms  discrete log: 3018 ms  ok
R-L: 3822  naive: 1498 ms  discrete log: 4025 ms  ok
R-L: 815730721  naive: 59 ms

#include <iostream>
#include <vector>
#include <algorithm>
#define NOMINMAX
#include <windows.h>
using namespace std;

vector<int> naive(int A, int P, int L, int R)
{
    vector<int> res;
    vector<bool> bitmap(P, false);

    int x = 1;
    while (true)
    {
        if (bitmap[x])
        {
            break;
        }
        bitmap[x] = true;
        if (x >= L && x <= R)
        {
            res.push_back(x);
        }
        x = (long long)x * A % P;
    }

    sort(res.begin(), res.end());
    return res;
}

vector<int> discretelog(int A, int P, int L, int R)
{
    int h = sqrt((double)P) + 1;
    vector<int> values(h + 1);

    int c = 1;
    values[0] = 1;
    for (int i = 1; i <= h; i++)
    {
        c = (long long)c * A % P;
        values[i] = (long long)values[i - 1] * A % P;
    }

    vector<bool> bitmap(P, false);
    int t = c;
    for (int i = 1; i <= h; i++)
    {
        bitmap[t] = true;
        t = (long long)t * c % P;
    }

    vector<int> res;
    for (int x = L; x <= R; x++)
    {
        for (int i = 0; i <= h; i++)
        {
            if (bitmap[(long long)values[i] * x % P])
            {
                res.push_back(x);
                break;
            }
        }
    }

    return res;
}

vector<int> solve(int A, int P, int L, int R)
{
    if (R - L < 2400)
    {
        return discretelog(A, P, L, R);
    }
    else
    {
        return naive(A, P, L, R);
    }
}

void test(int A, int P, int L, int R)
{
    LARGE_INTEGER start, end, freq;
    QueryPerformanceFrequency(&freq);
    cout << "R-L: " << R - L;

    QueryPerformanceCounter(&start);
    vector<int> resn = naive(A, P, L, R);
    QueryPerformanceCounter(&end);
    cout << "  naive: " << (end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart << " ms";

    if (R - L > 10000)
    {
        cout << endl;
        return;
    }

    QueryPerformanceCounter(&start);
    vector<int> resd = discretelog(A, P, L, R);
    QueryPerformanceCounter(&end);
    cout << "  discrete log: " << (end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart << " ms";

    bool correct = (resn.size() == resd.size());
    if (correct)
    {
        for (int i = 0; i < resn.size(); i++)
        {
            if (resn[i] != resd[i])
            {
                correct = false;
                break;
            }
        }
    }
    cout << (correct ? "  ok" : "  error") << endl;
}

int main()
{
    test(29, 999999937, 204411352, 204412600); // 124999993 / 1248
    test(7, 999999937, 450141522, 450142959);  // 111111105 / 1437
    test(32, 999999751, 239615046, 239616639); //  99999976 / 1593
    test(41, 999999937, 395909863, 395911989); //  76923073 / 2126
    test(6, 999999751, 217939683, 217942142);  //  66666651 / 2459
    test(6, 999999883, 724460982, 724463816);  //  55555550 / 2834
    test(35, 999999937, 399778083, 399780936); //  55555553 / 2853
    test(2, 999999937, 432617324, 432621146);  //  41666665 / 3822

    test(13, 815730721, 0, 815730721);  //  10 / 815730721
    return 0;
}