LOJ10202 樱花

题目

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

题解

因为正整数\(x,y\)，所以\(x,y>n!\)。
设\(x=n!+a\)，\(y=n!+b\)。\(a,b>0\)。
可以把式子化为\(a\times b=(n!)^2\)。
只要将\((n!)^2\)分解一下，约数个数是\(\prod_{i=1}^{k} q_i+1\)。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, P = 1e9 + 7;
int a, b, n, fac, cnt[N], prime[N], vis[N], tot;

void pri(int n) {
	vis[1] = 1;
    for(int i = 2; i <= n; i++) {
    	if(!vis[i]) prime[++tot] = i;
    	for(int j = 1; j <= tot && i * prime[j] <= n; j++) {
    	    vis[prime[j] * i] = 1;
    	    if(i % prime[j] == 0) break;	
    	}
    }
}
void calc(int x) {
	for(int i = 1; prime[i] * prime[i] <= x; i++) {
        while(x % prime[i] == 0) {
        	x /= prime[i];
        	cnt[prime[i]]++;
        }
	}
	if(x != 1) cnt[x] += 1;
}

int main() {
	cin >> n; pri(n);
	for(int i = 1; i <= n; i++) calc(i);
	int ans = 1;
    for(int i = 1; i <= n; i++) {
        ans = ans * 1ll * (cnt[i] * 2 + 1) % P;
    }
    cout << ans <<'\n';
    return 0;
}