【bzoj2440】[中山市选2011]完全平方数 莫比乌斯反演
2024-09-07 21:56:31
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
题解:https://wenku.baidu.com/view/fbec9c63ba1aa8114431d9ac.html
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio> #define N 50007
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int k;
int tot,flag[N],mu[N],pri[N]; void get_mu()
{
mu[]=;
for (int i=;i<=N;i++)
{
if (!flag[i])pri[++tot]=i,mu[i]=-;
for (int j=;j<=tot&&pri[j]*i<=N;j++)
{
flag[i*pri[j]]=;
if (i%pri[j]==){mu[i*pri[j]]=;break;}
else mu[i*pri[j]]=-mu[i];
}
}
}
bool check(int num)
{
int t=(int)sqrt(num);
ll sum=;
for (int i=;i<=t;i++)
sum+=mu[i]*num/(i*i);
return sum>=(ll)k;
}
int main()
{
get_mu();
int T=read(); while(T--)
{
k=read();
ll l=k,r=;
while(l<r)
{
ll mid=(l+r)>>;
if (check(mid)) r=mid;
else l=mid+;
}
printf("%d\n",l);
}
}
最新文章
- 【转】C#中将JSon数据转换成实体类,将实体类转换成Json
- c语言 sscanf()函数
- 缓存插件 EHCache 页面缓存CachingFilter
- CodeForces 86D Powerful array(莫队+优化)
- Leetcode: Kth Smallest Element in a Sorted Matrix
- oracle权限
- Android开发随笔4
- 输入adb shell 时 提示error: more than one device and emulator
- SPOJ QTREE4 lct
- 你的计算机也可以看懂世界——十分钟跑起卷积神经网络(Windows+CPU)
- Angular和Spring Boot一起做个项目
- 【dp】求最长公共子序列
- 各种15min(启动、横盘、破位)样例
- spring mvc重定向
- 【20181030T2】字胡串【分治+双指针】
- 【POJ2891】Strange Way to Express Integers(拓展CRT)
- BZOJ5296 CQOI2018 破解D-H协议 【BSGS】
- SQL注入导图
- 牛客网暑期ACM多校训练营(第五场)
- 趣学算法 PDF pdf 下载 陈小玉版
热门文章
- BOM属性对象方法
- dht 分布式hash 一致性hash区别
- hash join
- 转 Keras 保存与加载网络模型
- gradle更换国内镜像、配置本地仓库地址
- 【线性基合并 树链剖分】bzoj4568: [Scoi2016]幸运数字
- 【数位dp】bzoj3131: [Sdoi2013]淘金
- 【dp】饥饿的牛
- Fedora 28 系统基础配置以及常用软件安装方式
- 【mysql】【转发】Cannot proceed because system tables used by Event Scheduler were found damaged at server start