當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

P5221 Product（反演）

發(fā)布時(shí)間：2023/12/4 编程问答 26 豆豆

生活随笔收集整理的這篇文章主要介紹了 P5221 Product（反演）小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

P5221 Product

推式子

$∏i=1n∏j=1nlcm(i,j)gcd(i,j)∏i=1n∏j=1nijgcd(i,j)2我們考慮上面∏i=1n∏j=1nij∏i=1nin∏j=1nj∏i=1ninn!n!n∏i=1nin最后得到n!2n再考慮下面化簡(jiǎn)∏i=1n∏j=1ngcd(i,j)2∏d=1nd2∑i=1nd∑j=1nd[gcd(i,j)=1]對(duì)∑i=1nd∑j=1nd[gcd(i,j)==1]化簡(jiǎn)∑k=1ndμ(k)(nkd)2整體化簡(jiǎn)后n!2n∏d=1nd2∑k=1ndμ(k)(nkd)2\prod_{i = 1} ^{n} \prod_{j= 1} ^{n}\frac{lcm(i, j)}{gcd(i, j)}\\ \prod_{i = 1} ^{n} \prod_{j = 1} ^{n} \frac{ij}{gcd(i, j) ^ 2}\\ 我們考慮上面\\ \prod_{i = 1} ^{n} \prod_{j = 1} ^{n} ij\\ \prod_{i = 1} ^{n} i ^ n \prod_{j = 1} ^{n}j\\ \prod_{i = 1} ^{n} i ^ n n!\\ n! ^n \prod_{i = 1} ^{n} i ^ n\\ 最后得到n! ^{2n}\\ 再考慮下面化簡(jiǎn)\\ \prod_{i = 1} ^{n} \prod_{j = 1} ^{n}gcd(i, j) ^2\\ \prod_{d = 1} ^{n} d ^ {2\sum\limits_{i = 1} ^{\frac{n}ze8trgl8bvbq}\sum\limits_{j = 1} ^{\frac{n}ze8trgl8bvbq}[gcd(i, j) = 1]}\\ 對(duì)\sum_{i = 1} ^{\frac{n}ze8trgl8bvbq} \sum_{j = 1} ^{\frac{n}ze8trgl8bvbq} [gcd(i, j) == 1]化簡(jiǎn)\\ \sum_{k = 1} ^{\frac{n}ze8trgl8bvbq} \mu(k) \left(\frac{n}{kd}\right) ^ 2\\ 整體化簡(jiǎn)后\frac{n!^{2n}}{\prod_{d = 1} ^{n} d ^{2\sum\limits_{k = 1} ^{\frac{n}ze8trgl8bvbq} \mu(k) \left(\frac{n}{kd}\right) ^ 2}}$

代碼

開(kāi)c++17,不加 $O_2$ 能過(guò)，卡內(nèi)存，，，

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int mod = 104857601, Mod = mod - 1, N = 1e6 + 10;int mu[N], prime[N], cnt, n;bool st[N];ll quick_pow(ll a, int n) {ll ans = 1;while(n) {if(n & 1) ans = ans * a % mod;a = a * a % mod;n >>= 1;}return ans; }ll inv(ll x) {return quick_pow(x, mod - 2); }void init() {mu[1] = 1;for(int i = 2; i < N; i++) {if(!st[i]) {prime[cnt++] = i;mu[i] = -1;}for(int j = 0; j < cnt && 1ll * i * prime[j] < N; j++) {st[i * prime[j]] = 1;if(i % prime[j] == 0) break;mu[i * prime[j]] = -mu[i];}}for(int i = 1; i < N; i++) {mu[i] += mu[i - 1];} }ll calc1(ll l, ll r) {ll ans = 1;for(int i = l; i <= r; i++) {ans = ans * i % mod;}return ans; }ll calc2(ll n) {ll ans = 0;for(ll l = 1, r; l <= n; l = r + 1) {r = n / (n / l);ans = (ans + 1ll *(mu[r] - mu[l - 1]) * (n / l) % Mod * (n / l) % Mod) % Mod;}return (ans % Mod + Mod) % Mod; }int main() {init();scanf("%d", &n);ll a = 1, b = 1;for(int i = 1; i <= n; i++) a = a * i % mod;a = quick_pow(a, (2 * n) % Mod);for(int l = 1, r; l <= n; l = r + 1) {r = n / (n / l);b = b * quick_pow(calc1(l, r), 2ll * calc2(n / l) % Mod) % mod;}printf("%lld\n", 1ll * a * inv(b) % mod);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P5221 Product（反演）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

product