首页 > 代码库 > 【BZOJ2440】完全平方数 [莫比乌斯函数]
【BZOJ2440】完全平方数 [莫比乌斯函数]
完全平方数
Time Limit: 10 Sec Memory Limit: 128 MB[Submit][Status][Discuss]
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
1
13
100
1234567
Sample Output
1
19
163
2030745
19
163
2030745
HINT
对于 100% 的数据有 1 ≤ Ki ≤ 10^9, T ≤ 50
Main idea
询问第 k 个不含完全平方因子的数。
Source
显然我们可以简化一下问题,二分答案。那么我们就只需要知道:1~n中 不含完全平方因子 的数的个数。
然后我们思考一下容斥,用(总数-完全平方数个数):完全平方数个数 = 至少有1个质数平方因子的数 + 至少2个质数平方因子的数 - 至少3个质数平方因子的数……
也就是:奇数个质数平方因子的数 - 偶数个质数平方因子的数。
然后我们发现,那么可以枚举一个d,删除d^2相关,这时候系数也就是μ(d)。当d有奇数个质数因子的时候,删除的是有奇数个质数平方因子中d^2的倍数。
整理成式子也就是:
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 typedef long long s64;10 11 const int ONE = 44725;12 13 int T;14 int n,m;15 int prime[ONE],miu[ONE],isp[ONE],p_num;16 17 int get() 18 {19 int res=1,Q=1; char c;20 while( (c=getchar())<48 || c>57)21 if(c==‘-‘)Q=-1;22 if(Q) res=c-48; 23 while((c=getchar())>=48 && c<=57) 24 res=res*10+c-48; 25 return res*Q; 26 }27 28 void Getmiu(int MaxN)29 {30 miu[1] = 1;31 for(int i=2; i<=MaxN; i++)32 {33 if(!isp[i])34 isp[i] = 1, prime[++p_num] = i, miu[i] = -1;35 for(int j=1; j<=p_num, i*prime[j]<=MaxN; j++)36 {37 isp[i * prime[j]] = 1;38 if(i % prime[j] == 0)39 {40 miu[i * prime[j]] = 0;41 break;42 }43 miu[i * prime[j]] = -miu[i];44 }45 }46 }47 48 s64 Check(s64 n)49 {50 s64 res = 0 ,Q = sqrt(n);51 for(int d=1; d<=Q; d++)52 res += miu[d] * (n/(d*d));53 return res;54 }55 56 void Solve()57 {58 n = get();59 s64 l = 0, r = 2e9;60 while( l < r-1 )61 {62 s64 mid = (l+r)>>1;63 if(Check(mid) < n) l = mid;64 else r = mid;65 }66 67 if(Check(r) <= n) printf("%d", r);68 else printf("%d", l); 69 printf("\n");70 }71 72 int main()73 {74 Getmiu(ONE-1);75 T = get();76 while(T--)77 Solve();78 }79
【BZOJ2440】完全平方数 [莫比乌斯函数]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。