「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;
}