「一本通 6.2 练习 5」樱花（求不定方程）

题目描述

求不定方程：
$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$
的正整数解 (x,y) 的数目。

输入输出格式

输入格式

一个整数 n。

输出格式

一个整数，表示有多少对 $(x,y)$ 满足题意。答案对 $10^9+7$ 取模。

输入输出样例

输入样例#1：

2

输出样例#1：

3

提示信息

共有三个数对 $(x,y)$ 满足条件，分别是 $(3,6)$，$(4,4)$ 和 $(6,3)$。对于 $30$% 的数据，$n\le 100$；
对于全部数据，$1\le n\le 10^6$。

解法

#include <bits/stdc++.h>
using namespace std;
const int N=1e9+7;
long long n,k,s=1,l[2000000];
int main() {
	cin >>n;
	for (int i=2;i<=n;i++) {
		int t=i;
		for (int j=2;j*j<=t && t>0;j++) {
			while (t%j==0) {
				t/=j;
				l[j]++;
			}
		}
		if (t>1) l[t]++;
	}
	for (int i=2;i<=n;i++) {
		l[i]*=2;
		l[i]+=1;
	}
	for (int i=2;i<=n;i++) {
		s=s*l[i]%N;
	}
	cout <<s%N;
	return 0; 
}