【HDU】 1299 Diophantus of Alexandria

本文主要是介绍【HDU】 1299 Diophantus of Alexandria，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Diophantus of Alexandria

题目链接

Diophantus of Alexandria

题目大意

给定一个整数n，现在然你求有多少组x,y满足如下等式

1 x + 1 y = 1 n (x \leq y)

$\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\ \ \ \ \ \ (x≤y)$

题解

我们看到最小的y和最大的x同为2n，考虑到构造 $y=n+k$ ，这样我们求出 $x=\frac{n^2}{k}+n$ 又因为x小于y，所以我们可以求出 $k≥n$ ，x若要是整数，k必须是n^2的一个因子，所以问题转化为求n^2大于等于n的因子有多少个，实际上就是n^2的因子数+1再÷2
关于这个问题，我们可以先求n的因子数，再算出n^2的因子数。于是我们先把n质因数分解为

n = p e 1 1 p e 2 2 p e 3 3 . . . . . p e n n

$n=p_{1}^{e_1}p_2^{e_2}p_3^{e_3}.....p_n^{e_n}$
于是

n 2 = p 2 e 1 1 p 2 e 2 2 p 2 e 3 3 . . . . . p 2 e n n

$n^2=p_{1}^{2e_1}p_2^{2e_2}p_3^{2e_3}.....p_n^{2e_n}$
所以

n2 $n^2$ 的因子数为

(1 + 2 e 1) (1 + 2 e 2) (1 + 2 e 3) . . . . . (1 + 2 e n)

$(1+2e_1)(1+2e_2)(1+2e_3).....(1+2e_n)$
结果加一再除2即可。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>using namespace std;int T,n,tab[100005],vis[100005],h;void dealtab(int high)
{h=0;memset(tab,0,sizeof(tab));memset(vis,0,sizeof(vis));for (int i=2;i<=high;i++) if (!vis[i]){int j=i;tab[h++]=i;while(j<=high){vis[j]=1;j+=i;}}
}int main()
{int Case=1;scanf("%d",&T);dealtab(100000);while(T--){int cnt=0,ans=1;scanf("%d",&n);for (int i=0;i<h;i++){if (n==1) break;cnt=0;while (n%tab[i]==0){cnt++;n=n/tab[i];}ans*=(1+2*cnt);}if (n>3) ans*=3;printf("Scenario #%d:\n",Case++);printf("%d\n\n",(ans+1)/2);}return 0;
}