第13届景驰埃森哲杯广东工业大学ACM程序设计大赛随手记录帖

F：等式

思路：做以下解释：

首先考虑打表：由于x =y,有1/x =1/y,因此1/n-1/y =1/y，即y =2*n.这样，只需要在2*n范围之内枚举y，然后根据y尝试计算出x即可。这就是TOJ的题。但是！这里不行，因为n太大，每次循环如果数据都的是1e9，肯定会超时。

那么换种思路？

先看看暴力做的代码吧！

int sum = 0;
for(i=n+;i i++)
{if((i*n)%(i-n)==)
{
sum++;
}
}

注意看，是从n+1到n*2枚举(n*i)能否整除i-n；

那么做以下转化：

n*(n+k)/k  k属于[1,n]，求n*(n+k)/k是整数的k的个数。  发现式子可以化简为 n*n/k+1  。到这里，就好做了。 问题就转化为求n^2 中，在n之内的约数个数。

考虑到n^2是1e18次级，不太容易求。我们求n的约数即可。

做以下解释：12 = 2^2 * 3^1 约数个数为 指数+1的乘积。即(2+1)*(1+1) = 6

12^2 = 144 = 2^4 * 3 ^2  约数个数为 (4+1)*(2+1) = 15

可以看到，平方数的每一项都是原来的 (2倍指数值+1)

接下来就是欧拉函数+约数公式的问题了。最后注意一点。是如果最后剩下来的数如果是个大素数，那么别忘了乘以3。