ACM模版

描述

题解

这道数论题挺讲究技巧的，需要先通过原公式推出 N!^2 = (X - N!) * (Y - N!)，所以我们只需要求 N!^2 的约数个数。又因为 N!^2 = (p1^a1)^2 * (p2^a2)^2 * … * (pm^am)^2，所以我们只需要求出 2 * a1、2 * a2、2 * a3、…、2 * am，那么我们就需要求小于等于 N 的素数，然后对 1 ~ N （因为我们只需要求a1、a2、a3、…、am即可，这个与 1~N 有关）每个数进行质因数分解。因为题目中要求0 < x <= y，所以，最后结果为(1 + Π(2 * ai + 1)) / 2，最最后注意除法取模要用到逆元。挺有趣的一道问题……

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;

int vis[MAXN];

/* * 素数筛选，查找出小于等于MAXN的素数 * prime[0]存素数的个数 */
int prime[MAXN + 1];

void getPrime()
{
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i <= MAXN; i++)
    {
        if (!prime[i])
        {
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0] && prime[j] <= MAXN / i; j++)
        {
            prime[prime[j] * i] = 1;
            if (i % prime[j] == 0)
            {
                break;
            }
        }
    }
}

ll qPow(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n & 1)
        {
            ans = ans * a % MOD;
        }
        a = a * a % MOD;
        n >>= 1;
    }
    return ans;
}

int main()
{
    getPrime();

    int n;
    cin >> n;
    memset(vis, 0, sizeof(vis));

    for (int i = 1; i <= n; i++)
    {
        int k = i;
        for (int j = 1; j <= prime[0] && prime[j] * prime[j] <= k; j++)
        {
            if (k % prime[j] == 0)
            {
                while (k % prime[j] == 0)
                {
                    k /= prime[j];
                    vis[prime[j]] += 2;
                }
            }
        }
        if (k != 1)
        {
            vis[k] += 2;
        }
    }

    ll ans = 1;
    for (int i = 0; i <= MAXN; i++)
    {
        ans = ans * (vis[i] + 1) % MOD;
    }

    cout << (ans + 1) * qPow(2LL, MOD - 2) % MOD << endl;

    return 0;
}

参考

《素数相关》