自己做网站出证书,asp转换手机网站,怎么做app和网站购物车,宁波那家公司做网站好P5221 Product
推式子 ∏i1n∏j1nlcm(i,j)gcd(i,j)∏i1n∏j1nijgcd(i,j)2我们考虑上面∏i1n∏j1nij∏i1nin∏j1nj∏i1ninn!n!n∏i1nin最后得到n!2n再考虑下面化简∏i1n∏j1ngcd(i,j)2∏d1nd2∑i1nd∑j1nd[gcd(i,j)1]对∑i1nd∑j1nd[gcd(i,j)1]化简∑k1ndμ(k)(nkd)2整体化简后…P5221 Product
推式子
∏i1n∏j1nlcm(i,j)gcd(i,j)∏i1n∏j1nijgcd(i,j)2我们考虑上面∏i1n∏j1nij∏i1nin∏j1nj∏i1ninn!n!n∏i1nin最后得到n!2n再考虑下面化简∏i1n∏j1ngcd(i,j)2∏d1nd2∑i1nd∑j1nd[gcd(i,j)1]对∑i1nd∑j1nd[gcd(i,j)1]化简∑k1ndμ(k)(nkd)2整体化简后n!2n∏d1nd2∑k1ndμ(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}\\ 再考虑下面化简\\ \prod_{i 1} ^{n} \prod_{j 1} ^{n}gcd(i, j) ^2\\ \prod_{d 1} ^{n} d ^ {2\sum\limits_{i 1} ^{\frac{n}{d}}\sum\limits_{j 1} ^{\frac{n}{d}}[gcd(i, j) 1]}\\ 对\sum_{i 1} ^{\frac{n}{d}} \sum_{j 1} ^{\frac{n}{d}} [gcd(i, j) 1]化简\\ \sum_{k 1} ^{\frac{n}{d}} \mu(k) \left(\frac{n}{kd}\right) ^ 2\\ 整体化简后\frac{n!^{2n}}{\prod_{d 1} ^{n} d ^{2\sum\limits_{k 1} ^{\frac{n}{d}} \mu(k) \left(\frac{n}{kd}\right) ^ 2}} i1∏nj1∏ngcd(i,j)lcm(i,j)i1∏nj1∏ngcd(i,j)2ij我们考虑上面i1∏nj1∏niji1∏ninj1∏nji1∏ninn!n!ni1∏nin最后得到n!2n再考虑下面化简i1∏nj1∏ngcd(i,j)2d1∏nd2i1∑dnj1∑dn[gcd(i,j)1]对i1∑dnj1∑dn[gcd(i,j)1]化简k1∑dnμ(k)(kdn)2整体化简后∏d1nd2k1∑dnμ(k)(kdn)2n!2n
代码
开c17,不加O2O_2O2能过卡内存
#include bits/stdc.husing 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;
}
