一、题目链接
https://www.nowcoder.com/acm/contest/90/F
二、题面
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format: %lld 题目描述 给定n，求1/x + /y = /n （x<=y）的解数。（x、y、n均为正整数） 输入描述: 在第一行输入一个正整数T。 接下来有T行，每行输入一个正整数n，请求出符合该方程要求的解数。 （<=n<=1e9） 输出描述: 输出符合该方程要求的解数。 示例1 输入 输出
三、思路
由$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$，可推得：$x * n + y * n = x * y$，进一步可推得：$x*y-x*n-y*n+n^2 = n ^ 2$，即：$(x-n)(y-n)=n^2$。
题目要计算满足$x \le y$的解的个数。那么，从式子$(x-n)(y-n)=n^2$可以看出，$(x-n)(y-n)$相乘为$n^2$，即只要满足$n^2\ \% (x-n) = 0, n^2\ \% (y-n) = 0$就行。也就是，只要$(x-n)$和$(y-n)$为$n^2$的因子且$x \le y$就行了。
现在要计算$n^2$的因子个数，假设$f(n)$表示$n$的因子个数(下同)。比赛过程中，我尝试过打表，寻找$f(n)$和$f(n^2)$之间的关系，然而没找到。T_T。后来发现了这个公式：http://www.cnblogs.com/565261641-fzh/p/8641852.html。那么，$f(n^2) = f(p_1^{e_1^2} * p_2^{e_2^2} * p_3^{e_3^2} * \cdots * p_k^{e_k^2}) = (1+e_1^2) * (1+e_2^2) * (1+e_3^2) * \cdots * (1 + e_k^2)$。
另外需要注意的一点是，在分解$n$的质因子时，如果最后$n>1$，结果还需要乘以$(1 + 1 * 2)$即乘以$3$。解释一下，第一个$1$是上面的上述公式里面的；第二个$1$是$n = n^1$指数上的$1$，$2$也是上述公式里面的。
所求答案即为$\frac{f(n^2) + 1}{2}$。加$1$的原因是因为$n$在计算$f(n^2)$的过程中只算了一次。
四、源代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
;
template <class T> inline void read(T &x) {
int t;
bool flag = false;
')) ;
';
+ t - ';
if(flag) x = -x;
}
vector<int> ps;
];
void init() {
fill(, );
ps.clear();
] = ] = false;
; i < ; ++i) {
if(is[i]) {
; j += i)is[j] = false;
}
}
; i < ; ++i) {
if(is[i])ps.push_back(i);
}
}
LL calc(LL n) {
LL res = ;
;
; i * i <= n && idx < ps.size(); ++i) {
) {
;
) {
cnt++;
n /= ps[idx];
}
res *= ( + cnt * );
}
idx++;
}
)res *= ;
return res;
}
int main() {
#ifndef ONLINE_JUDGE
//freopen("input.txt", "r", stdin);
#endif // ONLINE_JUDGE
init();
LL n;
int T;
for(scanf("%d", &T); T--;) {
scanf("%lld", &n);
printf() / );
}
;
}