bzoj 2721: [Violet 5]樱花

题意：

求有多少对正整数$(x, y)$满足$\frac 1 x + \frac 1 y = \frac 1 {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("%lld\n", ans);
}