P4714 「数学」约数个数和 题解

· · 个人记录

P4714 「数学」约数个数和 题解

题目传送门

题意简述

因为变量名习惯不太一样，所以本文中 n 为原题面中的 N，本文中 m 为原体面中的 K。

给你一个正整数 n，请计算 n 的 ( 所有约数的 )\times m 约数个数和。

这个题意简述有点迷惑，建议还是去看原题面

写在前面

此题解写于题解通道关闭之后。

做的时候完全没往组合数上想。但是我非常自然地想出了这个解法 QwQ。

不计分解质因数的时间复杂度，我的做法是 O(\log^2 n \log m) 的。不如组合数做法的 O(\log n)。但是比这篇题解矩阵快速幂的 O(\log^3 n \log m) 要好。

原题因为卷的是 1 函数所以能组合数，如果卷的是其它积性函数说不定我的方法更方便？

前置知识

解法

规定记号：1(x)=1，d(x)=\sum\limits_{i|x}1。* 为狄利克雷卷积符号。

注意到其实就是求 (1 * 1 * \dots * 1 * d)(n)（m 个 1）的值。

首先 d = 1 * 1，所以原函数就是 m+2 个 1 卷起来。

狄利克雷卷积具有结合律。

一个运算只要有结合律就能快速幂。

一拍即合。

设 ans_{m+2}(n) 为答案。

注意到 ans 为一车积性函数的狄利克雷卷积，根据【积性函数卷积性函数还是积性函数】的性质，所以 ans 也是积性函数。

也就是说我们只需要考虑 ans 在质数的幂处的取值。（因为 O(\sqrt n) 朴素分解会 TLE，用 Pollard's rho 分解 n）

当 2\mid k 时：

ans_x = ans_{\frac x 2} * ans_{\frac x 2} ans_x(p^k)=\sum\limits_{i=0}^k ans_{\frac x 2}(p^i)ans_{\frac x 2}(p^{k-i})

否则：

ans_x = ans_{x-1} * 1 ans_x(p^k)=\sum\limits_{i=0}^k ans_{x-1}(p^i)

对于每个需要被计算的 ans_x，把 ans_x(p^0),ans_x(p^1),\dots,ans_x(p^k) 都算出来，为下一次卷积做准备。

因为 k 为 \log n 级别，所以时间复杂度 O(\log^2 n)。

用滚动数组可以把空间从 O(\log^2 n) 压到 O(\log n)。

结合快速幂，对于每个质数的幂计算 ans_m 的复杂度为 O(\log^2 n \log m)。

代码

因为不会 Pollard's rho 所以只有 83pts。加上 PR 应该就能过了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

// 省略快读快写的实现

const int MOD = 998244353;
const int LOGN = 65; // Log2[10^18]

LL n, m;
LL ans = 1;

LL f[2][LOGN];
int cur; // 滚动数组的索引
void qpow(int k, LL m) { // k 为 p^k 的 k
    if (m == 0) {
        memset(f, 0, sizeof(f));
        // 狄利克雷卷积单位元 epsilon
        f[cur][0] = 1;
    } else if (m & 1) {
        cur ^= 1;
        qpow(k, m - 1); // 算出 f_{m-1}(p^i)，存在 f[cur^1][i] 中
        cur ^= 1;
        for (int i = 0; i <= k; i++) {
            f[cur][i] = 0;
            for (int j = 0; j <= i; j++)
                (f[cur][i] += f[cur^1][j]) %= MOD;
        }
    } else {
        cur ^= 1;
        qpow(k, m >> 1); // 算出 f_{m>>1}(p^i)，存在 f[cur^1][i] 中
        cur ^= 1;
        for (int i = 0; i <= k; i++) {
            f[cur][i] = 0;
            for (int j = 0; j <= i; j++)
                (f[cur][i] += f[cur^1][j] * f[cur^1][i-j] % MOD) %= MOD;
        }
    }
}
LL solve(LL p, int k) { // 计算 p^k 的答案
    qpow(k, m + 2);
    return f[cur][k];
}

int main() {
    n = read(); m = read();

    // 朴素分解质因数，TLE 了
    for (LL i = 2; i * i <= n; i++) {
        int k = 0; while (n % i == 0)
            n /= i, k++;
        if (k) (ans *= solve(i, k)) %= MOD;
    }
    if (n != 1)
        (ans *= solve(n, 1)) %= MOD;

    write(ans);
    return 0;
}