首页 > 代码库 > 【BZOJ2440】完全平方数 [莫比乌斯函数]

【BZOJ2440】完全平方数 [莫比乌斯函数]

2024-09-12 00:06:05   217人阅读

完全平方数

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

Sample Output

　　1
　　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
View Code

 

【BZOJ2440】完全平方数 [莫比乌斯函数]


联系
我们