DDOSvoid's Blog

Luogu 「EZEC-3」四月樱花

发表于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目描述

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

简要题意：给定 $n$​​，求 $\prod_{x=1}^n\prod_{d|x}\frac{d^{\tau(d)}}{\prod_{t|d}(t+1)^2}$​​

$m\le 2.5\times 10^9$

Solution

我们首先对 $d^{\tau(d)}$ 下手，注意到该式等价于 $\prod_{t|d}d=\prod_{t|d}t\frac{d}{t}=(\prod_{t|d}t)^2$，这个变换再次展示了 $\prod$ 和 $\sum$ 的巨大区别 = =

那么我们现在的式子就是 $\prod_{x=1}^n\prod_{d|x}\prod_{t|d}\frac{t^2}{(t+1)^2}$​​​​，我们变换一下次序，容易得到 $\prod_{d=1}^n(\frac{d^2}{(d+1)^2})^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{di}\rfloor}$​​​​，指数上那个东西我们可以看成函数 $f(n)=\sum_{i=1}^n\lfloor\frac{n}{i}\rfloor=\sum_{i=1}^n\tau(i)$​​​​​，那么答案就是这个东西 $\prod_{d=1}^n(\frac{d^2}{(d+1)^2})^{f(\lfloor\frac{n}{d}\rfloor)}$​​​​，暴力算的话数论分块套数论分块的复杂度是 $O(n^{\frac 3 4})$ 的，不能通过此题，但我们预处理 $f$ 的前 $n^{\frac 2 3}$ 项就能做到 $O(n^{\frac 2 3})$

总的时间复杂度为 $O(\sqrt n\log n+n^{\frac 2 3})$

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
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define maxn 1500010
#define ll long long
#define uint unsigned int 
#define lowbit(i) ((i) & (-i))
using namespace std;

uint n;
int p, pp;

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; 
}

inline int add(int x, int y, int p = ::p) { return (x += y) >= p ? x - p : x; }

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

int calc_d(uint n) {
    if (n <= N) return d[n];
    int ans = 0; 
    for (uint l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans = add(ans, 1ll * (r - l + 1) * (n / l) % pp, pp);
    } return ans;
}

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

    cin >> n >> p; pp = p - 1; init_isp(N);
    ll ans = 1;
    for (uint l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l); 
        ll mul = 1ll * l * l % p * pow_mod(1ll * (r + 1) * (r + 1) % p, p - 2) % p;
        ans = ans * pow_mod(mul, calc_d(n / l)) % p;
    } cout << ans << "\n";
    return 0; 
}