因子个数_HDU_1299
这题就是要求1/x+1/y=1/n,给出n,算出满足条件的x,y对(x<=y).首先我们知道x和y都是大于n的,x<=2n,现在我们假设x=n+k(0<k<=n),那么y=n+n^2/k,我们知道y是整数,所以n^2一定是k的倍数,也就是k|n^2.这就要求我们求n^2的因子数了,OK,不过好像k还有限制条件- -|,其实我们可以先不考虑这个条件,因为x和y是对称的,所以算出总结过ans之后,ans’=(ans+1)>>1就是了.(加1是因为1/2n+1/2n=1/n这个式子只会出现一次).现在这题就变成了求一个数的因子数,我求因子数还是先分解素数做的,由于n^2实在太大,求sqrt(n^2)=n以内的素数也不可实现.其实我们只需要求出n的因子分解就行了,因为n^2=nn,那么因子的次方就是n的因子分解之后每个素数次方的2倍.这样这题就解决了,下面是代码:
1. #include
2. #include
3. #include
4. #include
5. const int MAX_N=6666;
6. int prime[MAX_N],idx;
7. int n;
8. void init_prime()
9. {
10. int i,j;
11. char p= (char )malloc(sizeof(char)65546);
12. memset(p,0,sizeof(char)65546);
13. for(i=2;i<65536;i+=2) <="" span="">
14. p[i]=1;
15. prime[0]=2;
16. idx=1;
17. for(i=3;i<65536;i+=2) <="" span="">
18. {
19. if(0 == p[i])
20. {
21. prime[idx]=i;
22. idx++;
23. if(i<257) <="" span="">
24. {/注意这里ii可能会越界/
25. for(j=ii;j<65536;j +="2*i)" <="" span="">
26. {
27. p[j]=1;
28. }
29. }
30. }
31. }
32. free(p);
33. }
34. void work()
35. {
36. int ans=1;
37. int i,j;
38. for(i=0;i
39. {
40. if(0 == (n%prime[i]))
41. {
42. j = 0;
43. while(0 == (n%prime[i]))
44. {
45. j++;
46. n /= prime[i];
47. }
48. ans = (2j+1);
49. }
50. if(1 == n)
51. {
52. break
53. }
54. }
55. if(n>1)
56. {
57. ans *= 3;
58. }
59. ans = (ans+1)>>1;
60. printf(“%d\n\n”,ans);
61. }
62. int main(void)
63. {
64. int t,i;
65. init_prime();
66. scanf(“%d”,t);
67. for(i=1;i<=t;i++)
68. {
69. scanf(“%d”,n);
70. printf(“Scenario #%d:\n”,i);
71. work();
72. }
73. return 0;
74. }
