Description

See OJ for details.

Solution

First of all, I think of 50 points of violence, and then I think of the answer to each prime number separately, and finally multiply, and the result hangs up.
According to the Chinese remainder theorem, positive solutions can be separated from each prime number.
\((x^m-x)\)%\(n=0\)
Since n\ has many different prime numbers, we can use the Chinese Remainder Theorem to decompose (c\) equations.
Then we get (x^m-x_0(mod~p)((c) equation)
We use 50 points of violence for each and multiply the final answer.
Time (O(T*c*t*logm)), 80 points.
Since there is a (log), we consider optimization.
According to the product sieve (Euler sieve), we can approach \\\\\\\\\\\\\\\
The prime number is directly calculated by (ksm) and the sum can be calculated by multiplying the value of its prime (y) and \(x/y\).
By eliminating (log), AC can be achieved.
Someone has spent (O(c*logpi)) time on this question.
Online%% dalao

Code

#include <cstdio>
#include <cstring>
#define N 51
#define ll long long
#define mo 998244353
#define mem(x, a) memset(x, a, sizeof x)
#define fo(x, a, b) for (int x = a; x <= b; x++)
#define fd(x, a, b) for (int x = a; x >= b; x--)
using namespace std;
int id, T, c, m, n, ans, s1;
int kz[10010], phi[N], pri[10010];

inline int read()
{
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}

int ksm(int x, int y)
{
    int s = 1;
    while (y)
    {
        if (y & 1) s = s * x % n;
        x = x * x % n; y >>= 1;
    }
    return s;
}

int main()
{
    freopen("division.in", "r", stdin);
    freopen("division.out", "w", stdout);
    id = read();
    T = read();
    while (T--)
    {
        c = read(), m = read();
        fo(i, 1, c) phi[i] = read();
        ans = 1;
        fo(i, 1, c)
        {
            s1 = 1; n = phi[i];
            fo(ii, 2, n) kz[ii] = 0;
            pri[0] = 0;
            fo(ii, 2, n)
            {
                if (! kz[ii]) kz[ii] = ksm(ii, m), pri[++pri[0]] = ii;
                for (int j = 1; pri[j] * ii <= n; j++)
                {
                    kz[pri[j] * ii] = kz[pri[j]] * kz[ii] % n;
                    if (ii % pri[j] == 0) break;
                }
                if (kz[ii] == ii % n) s1++;
            }
            ans = (ll)ans * s1 % mo;
        }
        printf("%d\n", ans);
    }
    return 0;
}