第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛 F 等式(数论，约数个数定理)

本文主要是介绍第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛 F 等式(数论，约数个数定理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给定n，求1/x + 1/y = 1/n （x<=y）的解数。（x、y、n均为正整数）

输入描述:

在第一行输入一个正整数T。 接下来有T行，每行输入一个正整数n，请求出符合该方程要求的解数。 （1<=n<=1e9）

输出描述:

输出符合该方程要求的解数。

输入

3
1
20180101
1000000000

输出

1
5
181

思路

关于这个方程的结论是:

所以我们只要求出$n^2$的约数个数就行了。

求约数个数有一个约数个数定理，详情请见:约数个数定理
就是任何一个数都可以分解成:

$$n={p_1}^{a_1}*{p_2}^{a_2}*{p_3}^{a_3}...$$
我们只需要求出:
$$(a_1+1)*(a_2+1)*...*(a_n+1)$$
的值就是答案。

因为这个题要满足条件$x≤y$所以对最后的结果$ans/2+1$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{ll t;ll n,ans,cnt;scanf("%lld",&t);while(t--){scanf("%lld",&n);ll temp=n*n;ans=1;for(ll i=2; i*i<=temp; i++){cnt=1;while(temp%i==0){cnt++;temp/=i;}ans*=cnt;}printf("%lld\n",ans/2+1);}
}

这篇关于第13届景驰-埃森哲杯广东工业大学ACM程序设计大赛 F 等式(数论，约数个数定理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---