Submission #69687948

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;
using ll = long long;
using db = double;
const ll N = 5500;
vector<ll> primes;
bool isprime[N + 1];
void eular()
{
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;
    for (ll i = 2; i <= N; i++)
    {
        if (isprime[i])
        {
            primes.push_back(i);
            for (ll j = i * i; j <= N; j += i)
                isprime[j] = false;
        }
    }
}
vector<vector<ll>> v;
ll m, T, a[N];
ll quickpow(ll a, ll b, ll md)
{
    a %= md;
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % md;
        b >>= 1;
        a = (a * a) % md;
    }
    return ans;
}
void solve()
{
    eular();
    ll cnt = primes.size();
    v.resize(N + 1, vector<ll>(cnt + 1, 0));
    for (ll i = 1; i <= N; i++)
    {
        v[i] = v[i - 1];
        ll z = i;
        for (ll j = 0; j < cnt && primes[j] <= z; j++)
        {
            while (z % primes[j] == 0)
            {
                v[i][j]++;
                z /= primes[j];
            }
        }
    }
    while (T--)
    {
        ll N;
        cin >> N;
        ll sum = 0;
        for (ll i = 0; i < N; i++)
        {
            cin >> a[i];
            sum += a[i];
        }

        vector<ll> v1 = v[sum];
        vector<ll> v2(cnt, 0);
        for (ll i = 0; i < N; i++)
        {
            for (ll j = 0; j < cnt; j++)
                v2[j] += v[a[i]][j];
        }

        ll ans = 1;
        for (ll i = 0; i < cnt; i++)
        {
            ll k = v1[i] - v2[i];
            if (k > 0)
                ans = (ans * quickpow(primes[i], k, m)) % m;
        }
        cout << ans << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> T >> m;
    solve();
}

Submission Info

Judge Result