生活随笔
收集整理的這篇文章主要介紹了
J. Product of GCDs（莫比乌斯反演）（2021牛客暑期多校训练营2）
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
Product of GCDs
∏d=1nd∑[gcd?(s1d,s2d,…,skd)=1]∏d=1nd∑i=1ndμ(i)Cf[id]k\prod_{d = 1} ^{n} d ^{\sum[\gcd(\frac{s_1}ze8trgl8bvbq, \frac{s_2}ze8trgl8bvbq, \dots, \frac{s_k}ze8trgl8bvbq) = 1]}\\ \prod_{d = 1} ^{n} d ^{\sum\limits_{i = 1} ^{\frac{n}ze8trgl8bvbq} \mu(i) C_{f[id]} ^{k}}\\ d=1∏n?d∑[gcd(ds1??,ds2??,…,dsk??)=1]d=1∏n?di=1∑dn??μ(i)Cf[id]k?
篩出質(zhì)數(shù)，然后得到phi(mod)phi(mod)phi(mod)，即可歐拉降冪寫（提供一個(gè)思路整體復(fù)雜度nlog?2nn \log ^ 2 nnlog2n了）。
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>using namespace std
;const int M
= 1e7 + 10, N
= 8e4 + 10, maxn
= 80000;int prime
[M
], mu
[M
], cnt
;int f
[N
], n
, k
;long long C
[N
][32], mod
, phi
;bool st
[M
];inline long long read() {long long 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
;
}void Init() {mu
[1] = 1;for (int i
= 2; i
< M
; i
++) {if (!st
[i
]) {prime
[++cnt
] = i
;mu
[i
] = -1;}for (int j
= 1; j
<= cnt
&& 1ll * i
* prime
[j
] < M
; j
++) {st
[i
* prime
[j
]] = 1;if (i
% prime
[j
] == 0) {break;}mu
[i
* prime
[j
]] = -mu
[i
];}}
}long long Phi(long long n
) {long long ans
= n
;for (int i
= 1; i
<= cnt
&& 1ll * prime
[i
] * prime
[i
] <= n
; i
++) {if (n
% prime
[i
] == 0) {ans
= ans
/ prime
[i
] * (prime
[i
] - 1);while (n
% prime
[i
] == 0) {n
/= prime
[i
];}}}if (n
> 1) {ans
= ans
/ n
* (n
- 1);}return ans
;
}long long mul(long long x
, long long y
) { return (__int128
)x
* y
% mod
;
}long long quick_pow(long long a
, long long n
) {long long ans
= 1;while (n
) {if (n
& 1) {ans
= mul(ans
, a
);}a
= mul(a
, a
);n
>>= 1;}return ans
;
}int main() {Init();int T
;T
= read();while (T
--) {n
= read(), k
= read(), mod
= read();for (int i
= 1; i
< N
; i
++) {f
[i
] = 0;}for (int i
= 1, x
; i
<= n
; i
++) {x
= read();f
[x
]++;}for (int i
= 1; i
<= maxn
; i
++) {for (int j
= 2 * i
; j
<= maxn
; j
+= i
) {f
[i
] += f
[j
];}}phi
= Phi(mod
);C
[0][0] = 1;for (int i
= 1; i
<= maxn
; i
++) {C
[i
][0] = 1;for (int j
= 1; j
<= 30; j
++) {C
[i
][j
] = C
[i
- 1][j
- 1] + C
[i
- 1][j
];if (C
[i
][j
] > phi
) {C
[i
][j
] -= phi
;}}}long long ans
= 1;for (int d
= 2; d
<= maxn
; d
++) {long long cur
= 0;for (int i
= 1; i
<= maxn
/ d
; i
++) {if (mu
[i
] == -1) {cur
-= C
[f
[i
* d
]][k
];if (cur
< 0) {cur
+= phi
;}}else if (mu
[i
] == 1) {cur
+= C
[f
[i
* d
]][k
];if (cur
> phi
) {cur
-= phi
;}}}ans
= mul(ans
, quick_pow(d
, cur
));}printf("%lld\n", ans
);}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的J. Product of GCDs（莫比乌斯反演）（2021牛客暑期多校训练营2）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
