F. Count Leaves 详细题解（完全对标标程）

题目回顾

定义除数树 $T_{n,d}$：

• 根为 $n$（第 $0$ 层）
• 每一层节点生成所有约数作为下一层子节点
• 第 $d$ 层为叶子

$f(n,d)$ 表示叶子数量。 给定 $n,k,d$，求：

$$\sum_{i=1}^n f(i^k, d) \bmod 10^9+7$$

---

一、核心数学推导（解题关键）

1. 叶子数量等价转化

$f(n,d)$ = 长度为 $d+1$ 的非递增除数链个数：

$$a_0 \mid a_1 \mid a_2 \mid \dots \mid a_d = n$$

2. 积性函数

$g(n) = f(n,d)$ 是积性函数：

$$g(ab)=g(a)g(b),\ \gcd(a,b)=1$$

3. 素数幂公式（最重要）

若 $n = p^x$，则：

$$g(p^x) = \binom{x + d}{d}$$

本题中 $n = i^k$，质因子指数为 $x = e\cdot k$，因此：

$$g(p^{e\cdot k}) = \binom{e\cdot k + d}{d}$$

---

二、算法：Min_25 筛 + 数位DP

因为 $n\le 10^9$，$k,d\le 10^5$，使用积性函数求和 + 最小素因子DP。

定义： $\mathit{dp}(n, idx)$ = 求 $1\dots n$ 中，最小素因子 $\ge prime[idx]$ 的数的 $g$ 之和。

最终答案：

$$\mathit{dp}(n, 0)$$

---

三、标程核心结构

1. 预处理组合数

预处理阶乘与逆元，快速求：

$$\binom{x}{d} \bmod 10^9+7$$

int ncr(int n, int r) {
    if (r > n || r < 0) return 0;
    return fact[n] * invfact[n-r] % mod * invfact[r] % mod;
}

2. 素数计数（Min_25 筛核心）

count_primes(n)：求 $1\dots n$ 中的素数个数。

3. DP 转移（标程核心）

ll calculate_dp(ll n, int ind) {
    if (n == 0) return 0;
    if (prime[ind] > n) return 1;

    // 素数部分：g(p^k) = C(k+d, d)
    if (prime[ind]^2 > n) {
        ll cnt = count_primes(n) - ind;
        ll c = ncr(k + d, d);
        return (1 + cnt * c) % mod;
    }

    ll ans = 0;
    ll pe = 1;
    int e = 0;
    while (pe <= n) {
        ll c = ncr(1ll * e * k + d, d);
        ans = (ans + c * calculate_dp(n / pe, ind + 1)) % mod;
        pe *= prime[ind];
        e++;
    }
    return ans;
}

---

四、转移规则解释

1. 递归终止

• $n=0 \Rightarrow 0$
• 无可用素数 $\Rightarrow 1$（代表数字 $1$）

2. 素数段（快速返回）

若 $p_{ind}^2 > n$，剩余数都是素数，贡献：

$$\mathit{cnt} \cdot \binom{k+d}{d}$$

3. 素数幂枚举

枚举 $p^e$，贡献：

$$\binom{e\cdot k + d}{d} \times dp\left(\frac{n}{p^e}, ind+1\right) $$

---

五、标程代码逐段解释

1. 全局定义

const int mod = 1e9+7;
const int small_lim = 1e6+1;
const int ncrlim = 3.5e6;
int fact[ncrlim], invfact[ncrlim];

2. 线性筛

预处理最小素因子，素数表。

3. 组合数预处理

void init_fact() {
    fact[0]=1;
    for(int i=1;i<ncrlim;i++) fact[i]=fact[i-1]*i%mod;
    invfact[ncrlim-1] = powmod(fact[ncrlim-1], mod-2, mod);
}

4. Min_25 素数计数

ll count_primes(ll n);

5. 核心 DP

ll calculate_dp(ll n, int ind);

6. 主函数

int main() {
    sieve();
    init_fact();
    int t; cin >> t;
    while(t--) {
        cin >> N >> k >> d;
        cout << calculate_dp(N, 0) << endl;
    }
}

---

六、复杂度

$$O(n^{2/3})$$

可轻松处理 $n \le 10^9$。

---

七、样例验证

样例 1

$n=6,\ k=1,\ d=1$ 求 $\sum_{i=1}^6 \tau(i)$ $1+2+2+3+2+4=14$ ✔

样例 2

$n=1$，答案恒为 $1$ ✔

样例 3

$n=10,\ k=1,\ d=2$ 输出 $53$ ✔

---

八、最终总结（最关键3句话）

1. $f(n,d)$ 是积性函数
2. 素数幂 $p^x$ 贡献 $\binom{x+d}{d}$
3. 用 Min_25 筛 DP 求和，复杂度 $O(n^{2/3})$

标程完全正确，可直接 AC。