2021牛客暑期多校训练营2 J. Product of GCDs

发表于 更新于 分类于

链接

https://ac.nowcoder.com/acm/contest/11253/J

题意

求大小为 $n$ $(1\le n\le 4e4)$ 的集合 $a$ $(1\le a_i \le 8e4)$ 中大小为 $k$ $(1\le k \le \min(n,30))$ 的子集的 $\gcd$ 的乘积，对 $p$ $(1e6\le p \le 1e14)$ 取模。

思路

考虑每个质因数对答案的贡献，记拥有因数 $p$ 且个数正好为 $i$ 个的数的个数为 $f_{p^i}$，可以容斥求出。

对于因数 $p^c$ ，对答案的贡献为 $p^{c\binom{f_{p^c}}{k}}$。

因为模数不一定为质数，且 $n$ 较小，我们可以递推求出组合数，枚举每个质因数的指数，并用扩展欧拉定理降幂，然而这样的做法不足以通过所有数据。

记拥有因数 $p^i$ 的数的个数为 $g_{p^i}$，我们可以发现 $p^{\binom{f_{p}}{k}}p^{2\binom{f_{p^2}}{k}}\dots p^{c\binom{f_{p^c}}{k}}=p^{\binom{g_{p}}{k}}p^{\binom{g_{p^2}}{k}}\dots p^{\binom{g_{p^c}}{k}}$。

因此我们可以直接对每个质因数计算贡献，这样只用对每个质因数求一次快速幂。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
// head
const int N=8e4;
int mn[10000001];
LL binom[40001][31];
int tot[N+5];
VI p;
void prime_seive(int n) {
    for(int i=2;i<=n;i++) {
        if(!mn[i]) mn[i]=i,p.PB(i);
        for(auto x:p) {
            if(x>mn[i]||x*i>n) break;
            mn[i*x]=x;
        }
    }
}
LL get_phi(LL n) {
    LL ret=n;
    for(int i=0,x=p[0];x*x<=n&&i<SZ(p);i++,x=p[i]) if(n%x==0) {
        while(n%x==0) ret=ret/x*(x-1),n/=x;
    }
    if(n>1) ret=ret/n*(n-1);
    return ret;
}
LL add(LL a,LL b,LL m) {
    return a+=b,a>=m?a-m:a;
}
LL mul(LL a,LL b,LL m) {
    return (__int128)a*b%m;
}
LL qpow(LL a,LL b,LL m) {
    LL ret=1;
    while(b) {
        if(b&1) ret=mul(ret,a,m);
        a=mul(a,a,m);
        b>>=1;
    }
    return ret;
}
void init(int n,int k,LL m) {
    binom[0][0]=1;
    for(int i=1;i<=n;i++) {
        binom[i][0]=1;
        for(int j=1;j<=min(i,k);j++) {
            binom[i][j]=add(binom[i-1][j-1],binom[i-1][j],m);
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    prime_seive(1e7);
    int T;cin>>T;
    while(T--) {
        memset(tot,0,sizeof tot);
        int n,k;LL m;cin>>n>>k>>m;
        for(int i=1;i<=n;i++) {
            int x;cin>>x;
            ++tot[x];
        }
        LL phi=get_phi(m);
        init(n,k,phi);
        LL res=1;
        for(auto x:p) {
            if(x>N) break;
            LL sum=0;
            for(LL i=x;i<=N;i*=x) {
                int cnt=0;
                for(int j=i;j<=N;j+=i) cnt+=tot[j];
                if(cnt<k) continue;
                sum+=binom[cnt][k];
            }
            if(sum>=phi) sum=sum%phi+phi;
            res=mul(res,qpow(x,sum,m),m);
        }
        cout<<res<<'\n';
    }
    return 0;
}