题意:完全平方数是指含有平方数因子的数。求第ki个非完全平方数。


解法:比较明显的二分,getsum(int middle)求1-middle有多少个非完全平方数,然后二分。求1-middle的非完全平方数个数可以用总数减掉完全平方数个数。计算完全平方数的个数用容斥:

    首先加上n/(2*2)+n/(3*3)+n/(5*5)+n/(7*7)...+...然后减掉出现两次的,然后加上三次的...奇加偶减。这就是mou的原型,用mou数组计算很简单;

       

代码:

 
  1. /******************************************************
  2. * @author:xiefubao
  3. *******************************************************/
  4. #pragma comment(linker, "/STACK:102400000,102400000")
  5. #include <iostream>
  6. #include <cstring>
  7. #include <cstdlib>
  8. #include <cstdio>
  9. #include <queue>
  10. #include <vector>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <map>
  14. #include <set>
  15. #include <stack>
  16. #include <string.h>
  17. //freopen ("in.txt" , "r" , stdin);
  18. using namespace std;
  19. #define eps 1e-8
  20. #define zero(_) (abs(_)<=eps)
  21. const double pi= acos( -1.0);
  22. typedef unsigned long long LL;
  23. const int Max= 100010;
  24. const LL INF= 2e16+ 7;
  25. LL mou[Max];
  26. void init()
  27. {
  28. for(LL i= 2; i<Max; i++)
  29. {
  30. if(!mou[i])
  31. {
  32. mou[i]=i;
  33. for(LL j=i*i; j<Max; j+=i)
  34. mou[j]=i;
  35. }
  36. }
  37. mou[ 1]= 1;
  38. for( int i= 2; i<Max; i++)
  39. {
  40. if(i/mou[i]%mou[i]== 0) mou[i]= 0;
  41. else mou[i]=-mou[i/mou[i]];
  42. }
  43. }
  44. int k;
  45. LL getnum(LL middle)
  46. {
  47. LL ans= 0;
  48. for(LL i= 1; i*i<=middle; i++)
  49. {
  50. ans+=mou[i]*(middle/(i*i));
  51. }
  52. return ans;
  53. }
  54. int main()
  55. {
  56. init();
  57. int t;
  58. cin>>t;
  59. while(t--)
  60. {
  61. scanf( "%d",&k);
  62. LL left= 1,right=INF;
  63. while(left<=right)
  64. {
  65. int middle=(left+right)/ 2;
  66. if(getnum(middle)<k)
  67. left=middle+ 1;
  68. else
  69. right=middle -1;
  70. }
  71. cout<<left<< '\n';
  72. }
  73. return 0;
  74. }