> 设1/n=1/(n+k)+1/p   p=n^2/k+n,但是答案并不是n^2的约数个数
> 观察例子:n=6,n^2=36,约数k=1,2,3,4,6,9,12,18,36对应的n+k为  7,8,9,10,12,15,18,24,42,对应的n+n^2/k为42,24,18,15,12,10,9,8,7,正好反过来了
> 而1/6=1/7+1/42与1/6=1/42+1/7在本题是没区别的，因此要去掉这些重复的部分
> 设n^2约数的个数为p,实际上除了n外的约数a[i]*a[p+1-i]=n^2,恰好一一对应，因此(p+1)/2就是答案
> 
> P.S求约数个数时只需分解n分解质因数（n^2的指数总是对应的2倍）,而分解n至多进行31607（小于sqrt(10^9)的最大质数）内的分解，且至多余下一个大于sqrt(10^9)的质数,不过本题稍微暴力一点似乎也可以

• Re:2917详细思路 (0) fhjmn112 2012-08-10 14:38:35
  • Re:2917详细思路 (0) fushit 2012-08-10 14:41:54
    • Re:2917详细思路 (0) fushit 2012-08-10 14:42:03