「JSOI2013」丢番图

发表于 | 分类于 | | 浏览量： 次

挺好玩的一个数学题。

传送门

洛谷P5253

BZOJ4459

题解

首先来看看题目中给出的式子，看起来不是很好搞：

分式不好搞，所以先给它乘开：

都移到一边：

化为两式相乘的形式：

不难发现，将$n^2$分解为任意两数相乘的形式时，都有唯一的$x,y$与之对应。

所以$n^2$的因子个数加一除以二就是答案。

但是$n^2$比较大，不好分解质因数。

但是$n$比较小，根据平方的性质，$n^2$的每一个质因子的个数等于$n$每一个质因子个数的两倍。

然后就好搞了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
using namespace std;
typedef long long LL;
int cnt,p[665000],tot[665000];LL n,ans;bool vis[10000005];
inline void make_p()          //欧拉筛素数
{
	vis[0]=vis[1]=true;
	for(int i=2;i<=10000000;i++)
	{
		if(!vis[i]){cnt++;p[cnt]=i;}
		for(int j=1;j<=cnt&&p[j]*i<=10000000;j++) vis[p[j]*i]=true;
	}
}
inline void Solve()
{
	for(int i=1;i<=cnt;i++)
		while(n%p[i]==0)
			{n/=p[i];tot[i]++;}   //分解质因数
	if(n>1){cnt++;tot[cnt]=1;p[cnt]=n;}
	ans=1;
	for(int i=1;i<=cnt;i++) ans*=2*tot[i]+1;   //计算因子个数
	ans=(ans+1)/2;
}
int main()
{
	make_p();
	scanf("%lld",&n);
	Solve();
	printf("%lld\n",ans);
	return 0;
}