bzoj 2721: [violet 5]樱花

求有多少对正整数$(x, y)$满足$frac 1 x + frac 1 y = frac 1 {n!}$

$$
frac 1 x + frac 1 y = frac 1 {n!} \
(x + y)n! = xy \
xn! + yn! - xy = 0 \
y = frac {xn!} {x - n!} \
y = frac {xn! - (n!) ^ 2 + (n!) ^ 2} {x - n!} \
y = n! + frac {(n!) ^ 2} {x - n!}
$$
所以答案就是$(n!) ^ 2$的约数个数，调和级数的复杂度搞就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int mod = 1000000007;
int n, s[1000010];
vector<int> prime;
bool is_prime[1000010];
long long ans = 1;

void pre(int n)
{
    memset(is_prime, 1, sizeof(is_prime));
    for (int i = 2; i <= n; i++)
    {
        if (is_prime[i])
        {
            prime.push_back(i);
        }
        for (int j = 0; j < prime.size() && prime[j] * i <= n; j++)
        {
            is_prime[prime[j] * i] = 0;
            if (i % prime[j] == 0) break;
        }
    }
}
int main()
{
    scanf("%d", &n);
    pre(n);
    for (int i = 0; i < prime.size(); i++)
    {
        int sum = 0;
        for (int j = prime[i]; j <= n; j += prime[i])
        {
            s[j] = s[j / prime[i]] + 1;
            sum += s[j];
        }
        ans = ans * (sum * 2 + 1) % mod;
        for (int j = prime[i]; j <= n; j += prime[i])
            s[j] = 0;
    }
    printf("%lldn", ans);
}