porumbei [90p] pbinfo.ro

#include <bits/stdc++.h>

using namespace std;
int n,a;
long long r=1;
bitset<2000002> rr;
ifstream f("porumbei.in");
ofstream g("porumbei.out");
stack<pair<int,int>> st;
int main()
{
    f>>a>>n;

    for(int i=1;i<=n;i++){
        r = (r*a)%n;  ///sume part
      ///  cout<<i<<" r="<<r<<endl;
        if(r==1){
            g<<"0 "<<i<<endl;
            return 0;

        }
        else{
            if(rr[(int)r]!=0){
                int ok=1;
                pair<int,int> elem;
                while(!st.empty() && ok){
                    elem=st.top();
                    //cout<<elem.first<<" "<<elem.second<<endl;
                    if(elem.first==(int)r){
                        ok=0;
                    }
                    st.pop();
                }
                g<<elem.second<<" "<<i;
                return 0;
            }
            else{
                rr[r]=1;
                st.push(make_pair((int)r,i));
            }
        }
    }
    return 0;
}