【BZOJ 2440】 2440: [中山市选2011]完全平方数（二分+容斥原理+莫比乌斯函数）-白红宇

【BZOJ 2440】 2440: [中山市选2011]完全平方数（二分+容斥原理+莫比乌斯函数）

阅读量：5284 次

发布时间：2019-06-14

本文共 1830 字，大约阅读时间需要 6 分钟。

2440: [中山市选2011]完全平方数

Description

小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些
数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而
这丝毫不影响他对其他数的热爱。
这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一
个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了
小X。小X很开心地收下了。
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？

Input

包含多组测试数据。文件第一行有一个整数 T，表示测试
数据的组数。
第2 至第T+1 行每行有一个整数Ki，描述一组数据，含义如题目中所描述。

Output

含T 行，分别对每组数据作出回答。第 i 行输出相应的
第Ki 个不是完全平方数的正整数倍的数。

Sample Input

4
1
13
100
1234567

Sample Output

1
19
163
2030745

HINT

对于 100%的数据有 1 ≤ Ki ≤ 10^9
, T ≤ 50

Source

【分析】

　　之前做的，现在竟然想不到了。。

　　二分。。。首先要知道这个数不会大于2*k【why？

　　然后求小于等于mid的有多少个满足的数。

　　可以知道如果这个数是某个数的平方的倍数，那么他分解质因数之后一定有一个的质数大于等于2

　　这里要想到容斥原理，就是ans=n-n/(2*2)-n/(3*3)-...+n/(6*6)+...-...+...

　　6因为是2和3的倍数，分解质因数之后有两个质因数，所以在容斥里面是加。

　　跟莫比乌斯函数很像吧？它的系数就是莫比乌斯函数啊，想想定义、、

　　真是太妙了【以后要多做点容斥的题目

　　这样是只要算到根号n的

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 #include
            
              7 #include
             
               8 using namespace std; 9 #define Maxn 10001010 #define LL long long11 12 LL mu[Maxn],pri[Maxn],pl;13 bool q[Maxn];14 15 LL mymin(LL x,LL y) { return x
              
               mx) break;32 q[i*pri[j]]=0;33 if(i%pri[j]==0) mu[i*pri[j]]=0;34 else mu[i*pri[j]]=-mu[i];35 if(i%pri[j]==0) break;36 }37 }38 39 }40 41 LL get_ans(LL n)42 {43 LL ans=0;44 LL sq=(LL)ceil(sqrt((double)n));45 for(LL i=1;i<=mymin(sq,n);i++)46 {47 ans+=mu[i]*(n/(i*i));48 }49 50 return ans;51 }52 53 LL ffind(LL k)54 {55 LL l=1,r=k*2;56 while(l
               
                >1;59 if(get_ans(mid)>=k) r=mid;60 else l=mid+1;61 }62 return l;63 }64 65 int main()66 {67 int T;68 T=1;69 scanf("%d",&T);70 get_mu(100000);71 while(T--)72 {73 LL n;74 scanf("%lld",&n);75 76 LL ans=ffind(n);77 78 printf("%lld\n",ans);79 }80 return 0;81 }