VIOLET5 樱花

wjh15101051's space

卧薪尝胆，厚积薄发。

VIOLET5 樱花

Date: Sun Oct 14 17:20:48 CST 2018

In Category: NoCategory

Description：

求 $\frac1x+\frac1y=\frac1{n!}$ 的正整数解个数。

$1\leqslant n\leqslant10^6$

Solution：

化一个式子得 $xy-(x+y)n!=0$ ，然后数学直觉好的话就会想到配一个 $(n!)^2$ ，于是有： $$ xy-(x+y)n!+(n!)^2=(n!)^2 $$

$$ (x-n!)(y-n!)=(n!)^2 $$

所以这题答案就是 $\sigma_0((n!)^2)$ ，线性筛一下素因子对每个素因子统计出现次数乘二然后求约数个数累乘就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

bool isprime[MAXN];

int prime[MAXN],tot = 0;

#define MOD 1000000007

int calc(int n,int k)

{

	int res = 0;

	for(int i = n;i != 0;i = i / k)res += i / k;

	return res * 2 + 1;

}

int main()

{

	scanf("%d",&n);

	for(int i = 2;i <= n;++i)isprime[i] = true;

	for(int i = 2;i <= n;++i)

	{

		if(isprime[i])prime[++tot] = i;

		for(int j = 1;j <= tot && i * prime[j] <= n;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)break;

		}

	}

	int ans = 1;

	for(int i = 1;i <= tot;++i)

	{

		ans = 1ll * ans * calc(n,prime[i]) % MOD;

	}

	cout << ans << endl;

	return 0;

}

In tag: 数学-线性筛

wjh15101051