603B - Moodular Arithmetic - CodeForces Solution

/**
 * author: deepanshu
 * created: 20-02-2023 02:19:09
**/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (ll i=a; i<(b); i++)
#define F0R(i, a) for (ll i=0; i<(a); i++)
#define mod 1000000007

#define getl(a) cin>>a;
#define init(a,n) for(ll i=0; i<n; i++) { cin>>a[i]; }
#define all(v) v.begin(),v.end()
void make_set(ll n, vector<ll> &parent, vector<ll> &ranks)
{
    for (ll i = 0; i < n; i++)
    {
        parent[i] = i;
        ranks[i] = 0;
    }
}

ll find_par(ll v, vector<ll> &parent)
{
    if (v == parent[v])
    {
        return v;
    }
    return parent[v] = find_par(parent[v], parent);
}

void union_set(ll u, ll v, vector<ll> &parent, vector<ll> &ranks)
{
    ll pu = find_par(u, parent);
    ll pv = find_par(v, parent);
    if (pu != pv)
    {
        if (ranks[pu] > ranks[pv])
        {
            parent[pv] = pu;
        }
        else if (ranks[pu] < ranks[pv])
        {
            parent[pu] = pv;
        }
        else
        {
            parent[pu] = pv;
            ranks[pv]++;
        }
    }
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll p,k,i,j;
    cin>>p>>k;
    vector<ll>parent(p),ranks(p);
    make_set(p,parent,ranks);
    map<ll,ll>mp,mp1;
    ll x=0;
    for(i=0;i<p;i++)
    {
        if(i==((i*k)%p))
        {
            x++;
        }
    }
    for(i=1;i<p;i++)
    {
        ll rem = (i*k)%p;
        if(rem!=0)
        {
            union_set(i,rem,parent,ranks);

        }
    }
    for(i=1;i<p;i++)
    {
        mp[find_par(i,parent)]++;
    }
    // cout<<mp.size();
    ll ans=1;
    for(i=0;i<mp.size();i++)
    {
        ans*=p;
        ans%=mod;
    }
    ans*=x;
    ans%=mod;
    cout<<ans;

    return 0;
}