# HackerEarth Partition it! problem solution

In this HackerEarth Partition it! problem solution Tubby the doggu, likes sets which are closed. Your task is to help him/her solve a problem.

Now the task is that you are given a prime number P and an array A of N integers , in which the ith integer is denoted by Ai, 1<=i<=N, 1<=Ai<=P.

You have to partition the set of indices {1,2,3,4,...,N} into a partition of minimum length such that if Closure({Ai}) subset of Closure({Aj}) then i and j must be in different sets of the partition.

Here, i!=j , 1<=i,j<=N.

## HackerEarth Partition it! problem solution.

`#include <bits/stdc++.h>#define ll long long#define pll pair<ll,ll>#define pil pair<int,ll>#define pli pair<ll,int>#define pii pair<int,int>#define mk make_pair#define pb push_back#define eps 1e-12#define MAXN 200009using namespace std;vector<ll> v;vector<int> ans[MAXN],out_g[MAXN];ll p;inline ll fastexpo(ll base,ll expo,ll mod){  ll result=1;  while(expo)  {    if(expo%2==1)    {      result=result*base;      result%=mod;    }    base=base*base;    base%=mod;    expo=expo/2ll;  }  return result;}inline void fact(ll n){  for(ll i=1;i*i<=n;i++)  {    if(n%i==0)    {      v.pb(i);      v.pb(n/i);    }  }  sort(v.begin(),v.end());}inline ll find_order(ll x){  for(int i=0;i<v.size();i++)  {    ll res=fastexpo(x,v[i],p);    if(res==1)    {      return v[i];    }  }  assert(false);}inline bool check_if_prime(ll n){  if(n==1||n==0)  {    return false;  }  for(ll i=2;i*i<=n;i++)  {    if(n%i==0)    {      return false;    }  }  return true;}int main(){  // ios_base::sync_with_stdio(false);  // cin.tie(0);  // cout.tie(0);  int t;  cin>>t;  assert(t<=100);  ll s=0;  while(t--)  {    v.clear();    ll n;    cin>>p>>n;    assert(check_if_prime(p));    s=s+n;    assert(p<=1000000000);    assert(p>=2);    assert(n<=1000);    ll a[n+1];    for(int i=1;i<=n;i++)    {      cin>>a[i];      assert(a[i]<p);      assert(a[i]>0);    }    fact(p-1);    pli ord[n+1];    for(int i=1;i<=n;i++)    {      ord[i]=mk(find_order(a[i]),i);      assert(((p-1)%ord[i].first)==0);    }    sort(ord+1,ord+n+1);    int indeg[n+1];    memset(indeg,0,sizeof(indeg));    for(int i=1;i<=n;i++)    {      for(int j=i+1;j<=n;j++)      {        if(ord[j].first%ord[i].first==0)        {          out_g[i].pb(j);          indeg[j]++;        }      }    }    int dp[n+1],maxx=0;    queue<int> q;    for(int i=1;i<=n;i++)    {      if(indeg[i]==0)      {        maxx=max(maxx,1);        dp[i]=1;        q.push(i);        ans[dp[i]].pb(i);      }    }    while(!q.empty())    {      int x=q.front();      q.pop();      maxx=max(maxx,dp[x]);      for(int i=0;i<out_g[x].size();i++)      {        indeg[out_g[x][i]]--;        if(!indeg[out_g[x][i]])        {          q.push(out_g[x][i]);          dp[out_g[x][i]]=dp[x]+1;          ans[dp[out_g[x][i]]].pb(out_g[x][i]);        }      }    }    cout<<maxx<<"\n";    // for(int i=1;i<=maxx;i++)    // {    //  for(int j=0;j<ans[i].size();j++)    //  {    //    cout<<a[ord[ans[i][j]].second]<<" ";    //  }    //  cout<<"\n";    // }    //clear    for(int i=0;i<=n;i++)    {      out_g[i].clear();      ans[i].clear();    }  }  assert(s<=25000);  //cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";}`

### Second solution

`#include <bits/stdc++.h>using namespace std;#define ll long longint A[1011];int dp[1011];ll bpow(ll x,ll n, ll mod) {    ll ans = 1;    while(n>0) {        if(n&1) ans*=x;        x*=x;        ans%=mod;        x%=mod;        n/=2;    }    return ans;}int main(){    int T;    cin >> T;    while(T--) {        int P,N;        cin >> P >> N;        vector<int>divs;        int sz = sqrt(P-1);        int num = P-1;        for(int j=1;j<=sz;j++) {            if(num%j==0) divs.push_back(j), divs.push_back(num/j);        }        sort(divs.begin(),divs.end());        vector<int>periods;        for(int i=0;i<N;i++) {            assert(cin >> A[i]);            assert(A[i]>=1 and A[i]<P);            ll cur = 1;            for(auto d:divs) {                if(bpow(A[i],d,P)==1){                    periods.push_back(d);                    break;                }            }        }        int maxLen  = 0;        sort(periods.begin(),periods.end());        for(int i=N-1;i>=0;i--) {            dp[i] = 1;            for(int j=i+1;j<N;j++) {                if(periods[j] % periods[i] == 0) dp[i] = max(dp[i], dp[j]+1);            }            maxLen = max(maxLen, dp[i]);        }        cout << maxLen << "\n";    }}`