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

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

Description

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

Input

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

Output

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

Sample Input

4
1
13
100
1234567

Sample Output

1
19
163
2030745

HINT

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

, T ≤ 50

Source

【分析】

之前做的&＃xff0c;现在竟然想不到了。。

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

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

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

这里要想到容斥原理&＃xff0c;就是ans&＃61;n-n/(2*2)-n/(3*3)-...&＃43;n/(6*6)&＃43;...-...&＃43;...

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

跟莫比乌斯函数很像吧&＃xff1f;它的系数就是莫比乌斯函数啊&＃xff0c;想想定义、、

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

这样是只要算到根号n的

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