Violet 樱花

约数个数 阶乘分解质因数 欧拉筛 T3

P1445 [Violet]樱花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目背景

又到了一年樱花盛开的时节。Vani 和妹子一起去看樱花的时候，找到了一棵大大的樱花树，上面开满了粉红色的樱花。Vani 粗略估计了一下，一共有足足 $n!$ 片花瓣。

Vani 轻柔地对她说：“你知道吗？这里面的一片花瓣代表着你，我从里面随机摘一片，能和你相遇的概率只有 $1/n!$ 那么小。我该是多么的幸运，才让你今天这么近地站在我面前。相信我，我一定会把这亿万分之一的缘分变为永远。”

粉红的樱花漫天飞舞，妹子瞬间被 Vani 感动了。她轻轻地牵起了他的手，和他相依而坐。这时，她突然看到田野的尽头也长着两棵樱花树，于是慢慢地把头靠在 Vani 的肩上，在他耳边低语：“看到夕阳里的那两棵樱花树了吗？其中一棵树上的一片花瓣是你，另一棵树上的一片花瓣是我，如果有人从这棵摘下一片，从那棵采下一瓣，我们相遇的概率会不会正好是 $1/n!$ 呢？”

Vani 的大脑飞速运作了一下，立即算出了答案。正要告诉妹子，她突然又轻轻地说：“以前你总是说我数学不好，但是这种简单的题我还是会算的。你看假如左边那棵树上有 $x$ 片花瓣，右边那个有 $y$ 片花瓣，那么我们相遇的概率不就是 $1/x+1/y$ 么，不过有多少种情况能使它正好可以等于 $1/n!$ 呢？这个你就帮我算一下吧～”

显然，面对天然呆的可爱妹子，Vani 不但不能吐槽她的渣数学，而且还要老老实实地 帮她算出答案哦。

题目描述

求方程：

$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$

的正整数解的组数，答案对 $10^9+7$ 取模。

输入格式

输入只有一行一个整数，表示 $n$。

输出格式

输出一行一个整数表示正整数解的组数模 $10^9+7$ 的值。

样例 #1

样例输入 #1

2

样例输出 #1

3

样例 #2

样例输入 #2

1439

样例输出 #2

102426508

提示

样例 1 解释

共有三个数对 $(x,y)$ 满足条件，分别是 $(3,6),(4,4)$ 和 $(6,3)$。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n\le 100$ 。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^6$。

思路

$n$ 的范围到 1e6， 求 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$ 满足等式的 $(x,y)$ 的正整数解方案数。

通分并移项得：$x\times n!+y\times n!=xy$ 这个式子的形式跟扩展欧几里得定理很像， 但没啥用。

一个方程要想得出满足条件的 $(x,y)$ 解个数， 得先枚举一个变量， 并通过两者间的关系得到另一个变量的值。

处理后得：$y=\frac{x\times n!}{x-n!}$ 。

依然没什么思路， 继续简化， 将分子分母的变量分离开： $y=\frac{(x-n!+n!)\times n!}{x-n!}=\frac{(x-n!)\times n!}{x-n!}+\frac{(n!{)}^2}{x-n!}=n!+\frac{(n!{)}^2}{x-n!}$

此时枚举所有正整数 x， 当 y 也是正整数时， 解$(x,y)$成立。

$n!$ 肯定是正整数， 而 $\frac{(n!{)}^2}{x-n!}$ 要想为整数， 需要满足 $x-n!$ 是 $(n!{)}^2$ 的约数。

再来看有没有可能 $x\le n!$ 而成立的情况， 根据 $\frac{1}{y}=\frac{1}{n!}-\frac{1}{x}$ 可知， $x>n!$ ， 否则 $y<0$ 不成立。

因此 $x-n!$ 不仅为 $(n!{)}^2$ 的约数， 还是正约数， 那么最终答案就是 $(n!{)}^2$ 的约数个数。

接下来是怎么求 $(n!{)}^2$ 的约数个数， 之前做过 $n!$ 的阶乘质因数分解， 策略就是先求出小范围的质数， 然后再枚举每个质数的乘方然后筛。

即阶乘 $n!$ 可分解为： $n!=p_1^{C_1}\times p_2^{C_2}\times \cdots \times p_k^{C_k}$ 那么对应的 $(n!{)}^2$ 也可分解为： $(n!{)}^2=p_1^{2C_1}\times p_2^{2C_2}\times \cdots \times p_k^{2C_k}$

再根据约数个数的方法即可求得 约数个数为 $(2C_1+1)(2C_2+1)\dots (2C_k+1)$

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, MOD = 1e9 + 7;
 
int primes[N], cnt;
bool st[N];
 
void init()
{
    for (int i = 2; i < N; i++)
    {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] * i < N; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)
                break;
        }
    }
}
 
void solve()
{
    int n, res = 1;
    cin >> n;
    for (int i = 0; i < cnt && primes[i] <= n; i++)
    {
        int p = primes[i], c = 0;
        for (int j = n; j; j /= p)
            c += j / p;
        res = (LL)res * (2 * c + 1) % MOD;
    }
    cout << res << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    solve();
    return 0;
}