题意：给n个数，求所有从这n个数中选k个构成一组的gcd的乘积
思路：因为每个数都可以分解为质数的乘积，所以我们考虑枚举gcd就是枚举所有质数以及他的倍数的gcd；假设现在有一个质数p，要取k个数使他的gcd为p，则只可能是p的倍数（2p，3p……），假设n个数*有m个p的倍数，则贡献就是；但是对于p²等p的幂次就相当于少算了（就是应该多乘几个p），所以把p的幂次也进行一次计算（实在不明白就找一个例子测试一下就行，反正我是想了很久还感觉迷迷糊糊的）
看不懂就借鉴这几篇文章吧：2021牛客多校 Product of GCDs（拓展欧拉定理+欧拉函数）_m0_51841071的博客-CSDN博客
队内训练2 牛客多校第二场补题J 拓展欧拉定理_ojbkoxy的博客-CSDN博客
总结一下：
1.枚举gcd，即枚举质数p以及它的所有幂次（当然要小于个数的最大值）
2.对于p或者他的幂次，计算这个数即他的倍数在n个数中出现的次数m
3.计算q=，最后每次枚举的结果就是p^q
注意：
1.k很大，用扩展欧拉降幂 (常数很大，你忍一下)
2.要用欧拉降幂，你又得知道欧拉函数
3.在求欧拉函数时，因为枚举常数会超时，所以你还需要枚举素数，所以你要求出所有素数
前置知识：
1.欧拉函数（f(x)代表小于等于x并与x互质的个数）：
对于p^n(p为质数)来说：f（p^n）=(p-1)p^(n-1);
证明：对于p^n,与他不互质的数只有0，p，2*p……p^n-p,共有p^n/p个，所以与他互质的数就有p^n-p^n/p=(p-1)p^(n-1);
然后是一般情况下，欧拉函数的计算流程。其中用到了前两个性质。把n质因数分解，然后把各个质因子带入最终公式，计算欧拉函数值。(节选自百度百科）
证明过程如图:
就用这个就可以写出暴力求n的欧拉函数的函数 phi（n）（之前不知道为什么脑子没有绕过弯，死活想不明白）：
ll phi(ll x)
{
__int128 ans=x;//超范围
for (int i=0;primes[i]<=x/primes[i];i++)//正常这里是枚举常数，但是因为超时，所以这里是枚举质数。。。离谱
//先除再乘，防止超范围
{
if (x%primes[i]==0)//prime[i]是x的质因数
{
ans=ans/primes[i]*(primes[i]-1);//套公式
while(x%primes[i]==0) x/=primes[i];//去除所有含有的这个质因子
}
}
if (x>1) ans=ans/x*(x-1);//x原本是素数的情况，没有质因子，特殊考虑
return ans;
}2.欧拉降幂：
欧拉定理、拓展欧拉定理及其应用（欧拉降幂法） - Reqaw - 博客园详细见此
3.最后快速幂就行
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 40010,M=10000010;
typedef long long ll;
int a[N];//真的怪，把这个数组改为a然后就超时，超时就算了，再改回来原来不超时的代码超时了！然后复制原来一模一样的代码交了，又能过了，真的离谱
//好了，我现在写个注释都会超时了
ll c[N][31];//计算组合数
int own[2*N];//计算每个数的次数
int prime[M],cnt;//根号P内的质数就行，因为我们是要求P的欧拉函数嘛
bool st[M];//是否为质数
int n, k;
ll P,euler;
//还要快读。。。这时间卡的
//大整数乘法：对于c=a?b的运算，由于a和b范围是10^14，直接乘会爆long long，
//因此可以用__int128做中间处理。
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch>'9')
{
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0'; ch = getchar();
}
return x * f;
}
inline ll lread()
{
ll x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch>'9')
{
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0'; ch = getchar();
}
return x * f;
}
void Isprime()//质数筛
{
for (int i = 2; i < M; i++)
{
if (!st[i])
{
prime[cnt++] = i;
for (int j = i * 2; j < M; j += i)
{
st[j] = true;
}
}
}
}
ll phi(ll x)//欧拉函数
{
__int128 ans = x;
for (int i = 0; x / prime[i] >= prime[i]; i++)
{
if (x % prime[i] == 0)
{
ans = ans / prime[i] * (prime[i] - 1);
while (x % prime[i] == 0)
{
x /= prime[i];
}
}
}
if (x > 1)
{
ans = ans / x * (x - 1);
}
return ans;
}
ll quick_mi(int p, ll m)//快速幂
{
__int128 ans = 1, base = p;
while (m)
{
if (m & 1)
{
ans = (ans * base) % P;
}
base = (base * base) % P;
m >>= 1;
}
return ans%P;
}
int main()
{
Isprime();
int t;
t = read();
while (t--)
{
memset(own, 0, sizeof(own));//记得清零！！！！！！
int Max = 0;
n = read(), k = read(), P = lread();
for (int i = 0; i < n; i++)
{
a[i]= read();
own[a[i]]++;
Max = max(a[i], Max);
}
euler = phi(P);
c[0][0] = 1;
for (int i = 1; i <= n; i++)//求组合数
{
c[i][0] = 1;
for (int j = 1; j <= min(k, i); j++)
{
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
if (c[i][j] >= euler)
{
c[i][j] = c[i][j] % euler + euler;//扩展定理
}
}
}
ll ans = 1;
for (int i = 0; prime[i] <= Max; i++)
{
for (int j = prime[i]; j <= Max; j *= prime[i])
{
int m = 0;
for (int q = j; q <= Max; q += j)
{
m += own[q];
}
if (m >= k)
{
ans = __int128(ans)* quick_mi(prime[i], c[m][k])%P;
}
else
{
break;//因为没退出wa了。。。。。
}
}
}
printf("%lld\n",ans%P);
}
return 0;
}欧拉公式延伸（这些没用到，但是了解一下挺好的，放最后吧）：
一个数所有的质因数的和=f(n)*n/2
（后面那句话是解释来着。。。）妙啊！！！震惊
wow，想明白了好神奇，反正就是这样