哇偶，看到标程之后才发现这题超级简单，只有求逆元，判素数，大数相乘三个函数和main函数中寥寥记剧就可以AC。

没知识真可怕，快来补一下.

这道题目主要用到了(p-2)! \equiv 1(\bmod \quad p)和快速求逆元\frac{1}{a}\equiv a^{p-2}(\bmod \quad p)

两个公式的条件都是p为质数。

另外还考察到了素数的密度分布，在大数里面质数分布的比较紧密，很快就可以在一个质数的附近找到另外一个质数。

即无需担心因为寻找/判定素数的时间过长而导致TLE

下面是标程代码：

#include <bits/stdc++.h>
using namespace std;

__int128 _a, _b, _m;
long long mul (long long a, long long b, long long m) 
{
	_a = a, _b = b, _m = m;
	return (long long)(_a * _b % _m);
}

long long inv (long long a, long long b, long long m) 
{
	long long ret = 1;
	while (b) 
       {
		if (b & 1) 
                    ret = mul(ret, a, m);
		a = mul(a, a, m);
		b >>= 1;
	}
	return ret;
}

inline bool check (long long n) 
{
	for (long long i = 2; i * i <= n; i++) 
        {
		if (n % i == 0) 
                     return true;
	}
	return false;
}

int main () 
{
	int kase;
	scanf("%d", &kase);
	while (kase--) 
        {
		long long p;
		scanf("%lld", &p);
		long long ret = p - 1, q = p - 1;
		while (check(q))
                {
			ret = mul(ret, inv(q, p - 2, p), p);
			q --;
		}
		printf("%lld\n", ret);
	}
}