#include <iostream>
#include <map>

using namespace::std;




void Input(int&a, int&B, int&N)
{
    cout << "Введите a,B,N: ";
    cin >> a >> B >> N;
}


int calcK(int N)
{
    return (int)(sqrt(N)) + 1;
}


int binpow(int value, int exponent, int modulo)
{
    long res = 1;
    while (exponent)
    {
        if (exponent & 1)
        {
            res *= value;
            res %= modulo;
        }
        value *= (value % modulo);
        value %= modulo;
        exponent >>= 1;
    }
    return res % modulo;
}


int ModPow(int base, int exp, int modulus)
{
    base %= modulus;
    int result = 1;
    while (exp > 0)
    {
        if (exp & 1) result = (result * base) % modulus;
        base = (base * base) % modulus;
        exp >>= 1;
    }
    return result;
}

map <int, int> BuildBigStepsTable(int k, int a, int N)
{
    map<int, int> ringspace;

    for (int i = 0; i < k; i++)
        ringspace[i] = ModPow(a, (i + 1)*k, N);
    return ringspace;

}


int GetSolution(map<int, int>BigSteps, int B, int a, int N)
{
    int BAPowJ;
    for (int i = 0; i < BigSteps.size(); i++)
    {
        BAPowJ = B*ModPow(a, i + 1, N);
        for (auto t : BigSteps)
        {
            if (BAPowJ == t.second)return calcK(N)*t.first - i;
        }

    }
    return -1;




}

bool DoMapContainValueInSecond(map<int, int> myMap, int value)
{
    for (auto t : myMap)
    {
        if (t.second == value)
            return true;
    }
    return false;
}

void PrintMap(map<int, int> mapToConsole)
{
    for (auto x : mapToConsole)
        cout << x.first << " " << x.second << endl;

}

// a^x =B(modN)
int main()
{
    setlocale(LC_ALL, "Russian");
    int a, B, N, k;

    Input(a, B, N);
    k = calcK(N);
    cout << "k:" << k << endl;

    map<int, int> BigSteps = BuildBigStepsTable(k, a, N);
    cout << "Big steps table:" << endl;
    PrintMap(BigSteps);
    cout << GetSolution(BigSteps, B, a, N) << endl;

    system("pause");
}