比赛 noip 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 __完全平方数 最终得分 100
用户昵称 Lethur 运行时间 3.429 s
代码语言 C++ 内存使用 18.75 MiB
提交时间 2016-11-04 20:06:06
显示代码纯文本
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cmath>
  4. using namespace std;
  5. const int m=100000007;
  6. int n,x,l;
  7. long long ans;
  8. int p[5000005],a[350000],b[350000];
  9. int main()
  10. {
  11. freopen("xnumber.in","r",stdin);
  12. freopen("xnumber.out","w",stdout);
  13. ans=1;
  14. cin>>n;
  15. x=int(sqrt(n));
  16. for(int i=2;i<=x;i++)
  17. if(p[i]==0)
  18. {
  19. int y=n/i;
  20. for(int j=2;j<=y;j++) p[i*j]=1;
  21. }
  22. for(int i=2;i<=n;i++)
  23. if(p[i]==0)
  24. {
  25. l++;
  26. a[l]=i;
  27. }
  28. for(int i=1;i<=l;i++)
  29. {
  30. x=n;
  31. while(x/a[i]>0)
  32. {
  33. x=x/a[i];
  34. b[i]=b[i]+x;
  35. }
  36. }
  37. for(int i=1;i<=l;i++)
  38. {
  39. if(b[i]%2==1) b[i]--;
  40. for(int j=1;j<=b[i];j++) ans=(ans*a[i])%m;
  41. }
  42. cout<<ans<<endl;
  43. return 0;
  44. }