比赛 noip 评测结果 AAAAAAAAAAAAAAAAAEEE
题目名称 __完全平方数 最终得分 85
用户昵称 芬特塞林斯 运行时间 1.267 s
代码语言 C++ 内存使用 18.42 MiB
提交时间 2016-11-04 20:42:14
显示代码纯文本
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<algorithm>
  4. #include<cmath>
  5. using namespace std;
  6.  
  7. const int maxn=500001;
  8. const int modof=100000007;
  9. long long int array[maxn],linein[maxn],getx,ans;
  10. long long int save1[maxn],save2[maxn];
  11. long long int find[maxn];
  12. long long int check;
  13. int n;
  14.  
  15. int main()
  16. {
  17. freopen("xnumber.in","r",stdin);
  18. freopen("xnumber.out","w",stdout);
  19. cin>>n;
  20. ans++;
  21. getx=sqrt(n);
  22. for(int i=2;i<=n;i++)
  23. {
  24. if(!linein[i])
  25. {
  26. int backi=n/i;
  27. for(int j=2;j<=backi;j++)
  28. {
  29. int pri=i*j;
  30. linein[pri]=1;
  31. }
  32. }
  33. }
  34. for(int i=2;i<=n;i++)
  35. {
  36. if(linein[i]==0)
  37. {
  38. save1[++check]=i;
  39. }
  40. }
  41. for(int i=1;i<=check;i++)
  42. {
  43. int geta=n;
  44. while(geta/save1[i]>0)
  45. {
  46. geta=geta/save1[i];
  47. save2[i]=save2[i]+geta;
  48. }
  49. }
  50. for(int i=1;i<=check;i++)
  51. {
  52. if(save2[i]%2==1)
  53. {
  54. save2[i]--;
  55. }
  56. for(int j=1;j<=save2[i];j++)
  57. {
  58. ans=(ans*save1[i])%modof;
  59. }
  60. }
  61. cout<<ans;
  62. return 0;
  63. }