#include <iostream>
#include <map>
using namespace::std;




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


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




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> BuildFirstSeri(int y,int a,int m,int p)
{
    map<int, int> seri;
    //map <int, int> otherseri;
    for (int i = 0; i < m; i++)
    {
        /*otherseri.insert(pair<int, int>(i,(int)pow(a,i)*y%p));*/
        seri.insert(pair<int, int>(i, y%p*ModPow(a, i, p)%p));
    }
    return seri;
}

int getSolution (map<int,int> firstseri,int a, int k,int p)
{
    cout << "Second seri: ";
    for (int i = 0; i < k; i++)
    {
        int tmpvalue=ModPow(a,(i+1)*k,p);

        cout << tmpvalue << " ";
        for (auto x : firstseri)
        {
            if (x.second == tmpvalue)
                return k*(i+1)-x.first;
        }

    }
    return -1;
}


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

}

// y=a^xmodp
int main()
{
    setlocale(LC_ALL, "Russian");
    int y, a, p,k,m;
    map<int, int> firstSeri;
    Input(a,p,y);
    k=m=calcK(p);
    cout << "k:" << k << endl;
    firstSeri = BuildFirstSeri(y, a, m,p);
    cout << "First seri:";
    PrintMap(firstSeri);
    cout <<endl<< "solution: " << getSolution(firstSeri, a, k, p)<<endl;



    system("pause");
}