洛谷1445 樱花

$$ \text{原式可以整理得到} \\ \frac{xy}{x+y}=n! \\ xy=\left( x+y \right) \times n! \\ \text{设}t=x+y,\text{则}y=t-x \\ x\left( t-x \right) =t\times n! \\ xt-x^2=t\times n! \\ t\left( x-n! \right) =x^2 \\ \text{设}k=x-n!,\text{则}x=k+n! \\ t=\frac{x^2}{k}=\frac{\left( k+n! \right) ^2}{k}=\frac{k^2+\left( n! \right) ^2+2\times k\times n!}{k}=k+2\times n!+\frac{\left( n! \right) ^2}{k} \\ \text{即} \\ t=k+2\times n!+\frac{\left( n! \right) ^2}{k} \\ \text{由于}t,k\text{都是整数，所以，根据}k=x-n!,n\text{确定时，每一个}k\text{可以确定一个唯一的}x\text{和}t\text{，进而确定唯一的}\left( x,y \right) \\ \text{所以答案为}\left( n! \right) ^2\text{的约数个数} $$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
typedef long long int int_t;
using std::cin;
using std::endl;
using std::cout;

const int_t LARGE = 1000000;
const int_t mod = 1e9 + 7;
int_t factor[LARGE + 1];
bool isPrime[LARGE + 1];
int_t times[LARGE + 1];
int main(){
    std::fill(isPrime + 2,isPrime + 1 + LARGE ,true);
    for(int_t i = 2;i <= LARGE ;i ++){
        if(isPrime[i]){
            for(int_t j = i * i;j <= LARGE ;j += i){
                isPrime[j] = false;
                factor[j] = i;
            }
            factor[i] = i;
        }
    }
    int_t n;
    cin >> n;
    for(int_t i = 2;i <= n;i++){
        int_t curr = i;
        while(curr != 1){
            int_t fac = factor[curr];
            times[fac] += 1;
            curr /= fac;
        }
    }
    int_t prod = 1;
    for(int_t i = 1;i <= n;i ++){
        prod = prod * (times[i] * 2 + 1) % mod;
    }
    cout << prod << endl;
	return 0;
}