P1445 [Violet]樱花

Link

一句话题意 ：

求 ({1 over x} + {1over y} = {1over n!}) 的解的个数。

很ex 的数学题，考场上没推出来柿子直接爆玲了，可怜。

首先我们把柿子化简一下，变成：

先通分 变成：

({x+y over xy} = {1over n!})

十字相乘之后移项可得：

((x+y) imes n! - xy = 0)

考试的时候，我推到这里就卡住了，完全不知道下一步怎么去推。

考完看了题解，才发现这是 十字相乘的右边的一部分柿子 就是类似于 ((a+x)(a+y)) 那样的柿子。

所以，我们给他左右两边同时加上一个 ({n!} ^2) 变成：

(n!^2 + (x+y)n! - xy = n!^2)

之后发现左边的柿子可以化为： ((n! - x) (n!-y) = n!^2)

也就是 令 (a = n!-x) (b = n!-y) ，则有 (ab = n!^2)

对于每个 (a,b) 他对应的 (x,y) 是唯一的，因此我们求的是 (n!^2) 的因子个数。

有唯一分解定理可得 (n = p_1^{k1} imes p_2^{k2} ..... imes p_n^{kn})

那么我们只需要求出 (n!) 的质因子的指数，最后的答案就是每个质因子指数乘二加一，最后在相乘。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
const int N = 1e6+10;
const int p = 1e9+7;
LL ans = 1;
int n,tot,cnt[N],prime[N];
bool check[N];
inline int read()
{
	int s = 0,w = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){s =s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
void YYCH()
{
	for(int i = 2; i <= n; i++)
	{
		if(!check[i])
		{
			prime[++tot] = i;
		}
		for(int j = 1; j <= tot && i * prime[j] <= n; j++)
		{
			check[i * prime[j]] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}
int main()
{
	n = read(); YYCH(); 
	for(int i = 1; i <= tot; i++)//枚举每个质数
	{
		for(LL j = prime[i]; j <= n; j *= prime[i])//质数的 j 次方的因子可以分出 j 个 i
		{
			cnt[i] += (n/j);
			cnt[i] %= p;
		}
	}
	for(int i = 1; i <= tot; i++)
	{
		ans = (ans * 1LL * (cnt[i] * 2+1)) % p;
	}
	printf("%lld
",ans);
	return 0;
}