求C(n,k)的欧拉函数φ(C(n,k))模1e9+7的高效算法

针对0≤k≤n<500000的场景，核心思路是通过组合数的质因数分解结合欧拉函数公式，全程在模1e9+7下运算，避免大整数溢出与低效因数分解。

步骤1：预处理核心数据 #

• 线性筛质数：用O(n)时间筛出5e5以内所有质数。这是处理大数质因数相关问题的基础，5e5规模完全无压力。
• 预处理阶乘的质因数指数：对每个质数p，用Legendre公式计算n!中p的指数：v_p(n!) = floor(n/p) + floor(n/p²) + floor(n/p³) + ...，直到p的幂超过n。后续C(n,k)中p的指数直接用v_p(n!) - v_p(k!) - v_p((n-k)!)得到，每个质数的计算时间是O(log_p n)，整体复杂度O(n log n)，完全可行。
• 预处理阶乘与逆元：
  • 计算fact[i] = i! mod MOD（MOD=1e9+7），递推即可：fact[i] = fact[i-1] * i % MOD。
  • 计算inv_fact[i] = (i!)^{-1} mod MOD，利用费马小定理，先算inv_fact[n] = pow(fact[n], MOD-2, MOD)，再逆推：inv_fact[i-1] = inv_fact[i] * i % MOD。

步骤2：计算φ(C(n,k)) #

欧拉函数公式：φ(m) = m * ∏(1 - 1/p)，其中p是m的所有不同质因数（即指数>0的质数）。我们分两部分计算：

• 计算C(n,k) mod MOD：直接用预处理的阶乘逆元：C = fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD。
• 计算乘积项∏(1-1/p) mod MOD：遍历所有预处理的质数p，若v_p(C(n,k)) > 0，则乘上(p-1) * pow(p, MOD-2, MOD) % MOD（因为1-1/p ≡ (p-1)*p^{-1} mod MOD），累积这个乘积。
• 合并结果：最终答案是(C * 乘积项) % MOD。

关键优势 #

• 避免了直接分解C(n,k)的低效操作，转而通过阶乘的质因数指数差得到组合数的质因数信息，效率极高。
• 全程模运算，彻底解决溢出问题，所有计算都在MOD范围内进行。
• 预处理只做一次，后续查询都是O(π(n))（π(n)是n以内质数数量，5e5时约4万），完全满足性能要求。

内容的提问来源于stack exchange，提问作者никита тюленев