Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#define maxN 500050
#define maxP 44444
#define fr(a,b,c) for (a=b;a<=c;a++)
#define frr(a,b,c) for (a=b;a>=c;a--)
using namespace std;

int test,n,z,P,s[maxN],d[maxN],A[maxN],st[maxN],last,sum[maxN],par[maxN],cur[maxN];
int p[maxP],r[maxP];
vector <int> a[maxN];


void prime()
{
  int i,j;
  fr(i,2,707)
    if (!d[i])
    {
      j=i*i;
      while (j<=maxN) d[j]=-1, j+=i;
    }
  fr(i,2,maxN)
    if (!d[i]) p[++P]=i, d[i]=P;
}

void dfsStack()
{
    st[++last]=1;
    while (last)
    {
        int x=st[last];
        if (cur[x]<int(a[x].size())) st[++last]=a[x][cur[x]++];
        else
        {
            last--;
            s[x]=sum[x]+1;
            for (int i=0;i+1<int(a[x].size());i++)
            {
                int y=a[x][i];
                A[sum[x]]++; A[sum[x]-s[y]]--; A[s[y]]--;
                sum[x]-=s[y];
            }
            sum[par[x]]+=s[x];
        }
    }
}

void calc()
{
   int i,j,x;
   frr(i,n,2)
   {
     A[i]+=A[i+1];
     if (A[i])
     {
         x=i; j=1;
         while (x>1 && d[x]<0)
         {
             while (x%p[j]==0) r[j]+=A[i], x/=p[j];
             j++;
         }
         if (x>1) r[d[x]]+=A[i];
     }
   }
   long long re=1;
   fr(i,1,maxP)
     while (r[i]) r[i]--, re=(re*p[i])%z;
   cout << re << endl;
}

int main()
{
  int i;
  prime();
  cin >> test;
  while (test--)
  {
    cin >> z >> n;
    fr(i,2,n)
    {
      scanf("%d",&par[i]);
      a[par[i]].push_back(i);
    }
    dfsStack();
    calc();
    if (test) fr(i,1,n+1) A[i]=sum[i]=s[i]=cur[i]=0, a[i].clear();
  } 
  return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>

const int N = 500005;

using namespace std;

int sz[N], par[N], nChild[N], np[N], cnt[N], P[N];
int n, MOD, nTest, nPrime;

long long power(long long a, int p) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = ans * a % MOD;
    a = a * a % MOD;
    p >>= 1;
  }
  return ans;
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  for (int i = 2; i * i < N; ++i)
  if (!np[i])
    for (int j = i * i; j < N; j += i)
      np[j] = i;
  for (int i = 2; i < N; ++i)
  if (!np[i]) {
    np[i] = i;
    P[nPrime++] = i;
  }
  cin >> nTest;
  while (nTest--) {
    cin >> MOD >> n;
    for (int i = 2; i <= n; ++i) {
      cin >> par[i];
      ++nChild[par[i]];
    }
    queue<int> Q;
    for (int i = 1; i <= n; ++i) {
      sz[i] = 1;
      if (nChild[i] == 0) Q.push(i);
    }
    while (!Q.empty()) {
      int u = Q.front(); Q.pop();
      sz[par[u]] += sz[u];
      if ((--nChild[par[u]]) == 0)
        Q.push(par[u]);
    }
    for (int i = 0; i < nPrime; ++i)
      for (long long j = P[i]; j < sz[1]; j *= P[i])
        cnt[P[i]] += (sz[1] - 1) / j;
    for (int i = 2; i <= n; ++i)
      for (int x = sz[i]; x > 1; x /= np[x])
        --cnt[np[x]];
    long long ans = 1;
    for (int i = 0; i < nPrime; ++i)
    if (cnt[P[i]]) {
      ans = ans * power(P[i], cnt[P[i]]) % MOD;
      cnt[P[i]] = 0;
    }
    cout << ans << '\n';
  }
  return 0;
}

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

int nprime, prime[500111];
bool sieve[500111];

void init() {
    FOR(i,2,720)
    if (!sieve[i]) {
        int j = i * i;
        while (j <= 500000) {
            sieve[j] = true;
            j += i;
        }
    }
    FOR(i,2,500000)
        if (!sieve[i]) prime[nprime++] = i;
}

ll base;
int n, sz[500111], d[500111], vao[500111];
vector<int> ke[500111];

int st[500111], top, last[500111];

void dfs() {
    top = 1; st[1] = 1;
    FOR(i,1,n) sz[i] = 1;
    memset(last, 0, sizeof last);

    while (top) {
        int u = st[top];
        if (last[u]) sz[u] += sz[ke[u][last[u]-1]];
        if (last[u] < ke[u].size()) {
            int v = ke[u][last[u]];
            st[++top] = v;
            ++last[u];
        }
        else --top;
    }
}

ll power(ll x, int k) {
    if (k == 0) return 1;
    if (k == 1) return x % base;
    ll mid = power(x, k >> 1);
    mid = (mid * mid) % base;
    if (k & 1) return (mid * x) % base;
    else return mid;
}

int get(int n, int p) {
    if (n < p) return 0;
    return n/p + get(n/p,p);
}

void remove(int n) {
    REP(x,nprime) {
        if (prime[x] * prime[x] > n) break;
        int k = 0;
        while (n % prime[x] == 0) {
            n /= prime[x];
            k++;
        }
        d[x] -= k;
    }
    if (n > 1) {
        int x = lower_bound(prime, prime+nprime, n) - prime;
        d[x]--;
    }
}

//Buffer reading
int INP,AM;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (feof(stdin)) memset(BUF, 0, sizeof BUF); else fread(BUF,1,BUFSIZE,stdin); \
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    init();
    int test; GN(test);
    while (test--) {
        GN(base); GN(n);
        FOR(i,1,n) ke[i].clear();
        int u;
        FOR(i,2,n) {
            GN(u);
            ke[u].PB(i);
        }
        dfs();

        REP(x,nprime) d[x] = get(n-1, prime[x]);
        FOR(i,2,n) remove(sz[i]);

        ll res = 1;
//        REP(x,nprime) cout << d[x] << ' '; cout << endl;
        REP(x,nprime) res = (res * power(prime[x], d[x])) % base;
        cout << res; puts("");
    }
    return 0;
}

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00000001
#define oo 1111111111
#define mod 1000000007
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
//#include <conio.h>
//#define g 9.81
#define maxn 500005
double const PI=4*atan(1.0);

const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

int test, n, m;
int adj[maxn], last[maxn], next[maxn], E, x;
int a[maxn], num[maxn];

bool isprime[maxn];
int f[maxn], dad[maxn];

void init(){
    memset(isprime, 1, sizeof(isprime));
    FOR(i, 2, 1000) if(isprime[i]){
        for(int j = i * i ; j < 500000; j += i){
            isprime[j] = 0;
            f[j] = i;
        }
    } 

    FOR(i, 2, 500000) if(isprime[i]){
        f[i] = i;
    } 
}


void duyet(int u){

    int que[maxn], size = 0;
    que[size++] = u;

    rep(i, size){
        u = que[i];
        for(int e = last[u]; e != -1; e = next[e]){
            int v = adj[e];
            que[size++] = v;
        }
    }

    FOR(i, 1, n) a[i] = 1;
    FORD(i, size - 1, 0) {
        u = que[i];
        a[dad[u]] += a[u];
    }
}

long long mu(int x, int a, int modun){
    if(a == 0) return 1;
    long long t = mu(x, a >> 1, modun);
    if(a & 1) return (((t * t) % modun) * x) % modun;
    return (t * t) % modun;
}


int main(){ 
  //  OPEN();
    clock_t start = clock();
    init();
   // printf("%d\n", clock() - start);

    gi(test);

    while(test--){

        gi(m); gi(n);
        memset(last, -1, sizeof(last));
        E = 0;
        FOR(i, 2, n){
            gi(x);
            adj[E] = i; dad[i] = x; next[E] = last[x]; last[x] = E++;
        }

      //  printf("%d\n", clock() - start);
        duyet(1);

        FOR(i, 1, n - 1) num[i] = 0;
      //  printf("%d\n", clock() - start);

        FOR(i, 2, n - 1) if(isprime[i]){
            int the = n - 1, res = 0;
            while(the){
                num[i] += the / i;
                the /= i;
            }
        }
      //  printf("%d\n", clock() - start);

        //cout << "ok" << endl;
        FOR(i, 2, n){
            int the = a[i];
            while(the != 1 && the != 0){
                num[f[the]]--;
                the /= f[the];
            }
        }
      //  printf("%d\n", clock() - start);

        long long res = 1;
        FOR(i, 2, n - 1) if(num[i] > 0){
            res = (res * mu(i, num[i], m)) % m;
        }

        printf("%lld\n", res);
    }
   // printf("%d\n", clock() - start);
}