Luogu P5221 Product

题目描述

https://www.luogu.com.cn/problem/P5221

简要题意：求 $\prod_{i=1}^n\prod_{j=1}^n\frac{[i,j]}{(i,j)}\bmod 104857601$

$n\le 10^6$

Solution

$$\begin{aligned} ans&=\prod_{i=1}^n\prod_{j=1}^n\frac{[i,j]}{(i,j)}\\ &=\prod_{i=1}^n\prod_{j=1}^n\frac{ij}{(i,j)^2}\\ &=(n!)^{2n}\prod_{t=1}^n\prod_{i=1}^n\prod_{j=1}^nt^{-2}[(i,j)=t]\\ &=(n!)^{2n}\prod_{t=1}^n(t^{\sum_{i=1}^n\sum_{j=1}^n[(i,j)=t]})^{-2}\\ &=(n!)^{2n}\prod_{t=1}^n(t^{2\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\varphi(i)-1)})^{-2} \end{aligned}$$

预处理 $O(n)$，单次 $O(\sqrt n\log n)$

#include <iostream>
#define maxn 1000010
#define ll long long
using namespace std;

const int p = 104857601;
const int pp = 104857600;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s; 
}

int pri[maxn / 10], cnt, phi[maxn]; bool isp[maxn];
void init_isp(int n) {
    phi[1] = 1; 
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, phi[i] = i - 1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            } phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }
    for (int i = 1; i <= n; ++i) phi[i] = (phi[i] + phi[i - 1]) % pp;
}

int n;

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; init_isp(n); ll mul = 1, fac = 1;
    for (int i = 1; i <= n; ++i) fac = fac * i % p; 
    for (int l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l); ll fac = 1; 
        for (int i = l; i <= r; ++i) fac = fac * i % p;
        mul = mul * pow_mod(fac, 2 * phi[n / l] + pp - 1) % p;
    } cout << pow_mod(mul * mul % p, p - 2) * pow_mod(fac, 2 * n) % p << "\n";
    return 0;
}