基础数学算法-樱花

题目-樱花

问题分析

对原式进行变形
$$x+y=\frac{xy}{n!}$$
也就是
$$x\cdot n!+y\cdot n!=xy$$

只要$x$固定$y$也就固定了, 因此推导一下$x$与$y$之间的关系

$$y=\frac{x\cdot n!}{x-n!}$$

$x\in Z^{+}$, 求$y$是正整数的方案数量

因为当前式子还是没办法直接计算, 继续对式子进行变形

$$y=\frac{(x-n!+n!)\cdot n!}{x-n!}=n!+\frac{n{!}^2}{x-n!}$$

因为$n!$是正整数, 不需要考虑

又因为
$$\frac{1}{y}=\frac{1}{n!}-\frac{1}{x}$$

问题变成了$x$如何取值, 使得$(x-n!)|n{!}^2$, 并且

$x>n!$, 否则$y$就是负数, 是矛盾的

因为分母$x-n!$一定是正数, 满足条件的$x$的个数等价于满足条件的$x-n!$的个数, 也就等于了$n{!}^2$的约数个数

算法步骤

• 首先对$n!$进行分解质因数, 得到$n!=p_1^{k_1}{p}_2^{k_2}...p_k^{k_n}$
• $(n!{)}^2$的约数个数等于$(2k_1+1)(2k_2+1)...(2k_n+1)$

对于每个指数$p$, 计算的项数条件是$p^m\le n$, $m\le \log n$
因此算法时间复杂度$O(n\log n)$

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1e6 + 10, MOD = 1e9 + 7;

int n;
int primes[N], cnt;
bool st[N];

void init(int k) {
   
    for (int i = 2; i <= k; ++i) {
   
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= k / i; ++j) {
   
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

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

    cin >> n;
    init(n);

    LL ans = 1;
    for (int i = 0; i < cnt; ++i) {
   
        int p = primes[i];

        LL cnt = 0;
        for (int j = n; j; j /= p) cnt += j / p;

        ans = ans * (2 * cnt % MOD + 1) % MOD;
    }

    cout << ans << '\n';
    return 0;
}