[bzoj2440]完全平方数(二分+mobius反演)
2024-09-29 17:47:46
解题关键:由容斥原理得,num=1的倍数的数量−一个质数平方数(9,25,49...)的倍数的数量+两个质数的积平方数(36,100,225...)的数量−三个质数......
这道题用莫比乌斯的正向函数表达式理解较容易
此题让自己理解了只要与倍数相关即可用mobius。
此题还需要注意的一点,是平方数只需要反演质数。貌似是常识
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long ll;
ll t,n;
inline ll read(){
char k=;char ls;ls=getchar();for(;ls<''||ls>'';k=ls,ls=getchar());
ll x=;for(;ls>=''&&ls<='';ls=getchar())x=(x<<)+(x<<)+ls-'';
if(k=='-')x=-x;return x;
}
//莫比乌斯函数线性筛法
const int maxn=+;
bool vis[maxn];
int prime[maxn],mu[maxn];
void init_mu(int n){
int cnt=;
mu[]=;
for(int i=;i<n;i++){
if(!vis[i]){
prime[cnt++]=i;
mu[i]=-;
}
for(int j=;j<cnt&&i*prime[j]<n;j++){
vis[i*prime[j]]=;
if(i%prime[j]==) {mu[i*prime[j]]=;break;}
else { mu[i*prime[j]]=-mu[i];}
}
}
} bool check(ll x){
ll ans=;
for(ll i=;i*i<=x;i++){
ans+=mu[i]*(x/(i*i));
}
return ans>=n;
} ll erfen(ll l,ll r){
while(l<r){
ll mid=(l+r)>>;
if(check(mid)) r=mid;
else l=mid+;
}
return r;
}
int main(){
init_mu();
t=read();
while(t--){
n=read();
printf("%lld\n",erfen(, ));
} }
最新文章
- 【转载】兼容php5,php7的cURL文件上传示例
- 虚拟机安装Centos7 , 没有可用的网络设备【ifconfig 只有lo而没有eth0的解决办法】
- 根据多年经验整理的《互联网MySQL开发规范》
- VS中Debug和Realease、及静态库和动态库的区别整理
- Ruby on Rails Tutorial 第六章 用户模型
- Struts个人总结
- PyCharm 5.0.3 快捷键
- LEK-Introduction
- 格式化JSON字符串
- 03-TypeScript中的强类型
- java集合框架07——Map架构与源代码分析
- day92之支付宝支付
- HDU4288-STL模拟
- asp.net core模块学习
- mvc 模型验证及正则表达式
- SpringMVC 示例实战教程
- H5中JavaScript常用代码片段
- HDUOJ--畅通工程
- 【VIJOS】P1512 SuperBrother打鼹鼠
- 转:Andriod studio技巧合集
热门文章
- Android 事件分发机制 图解
- Python中的注解“@” 、Java 注解
- DockPanel的使用与技巧
- 小程序的生命周期 launchApp
- java基础语言 运算符
- ERR:/usr/local/lib/libcrypto.so.1.0.0: no version information available
- web 全栈 学习 2 一个好的页面是如何炼成的
- debian下编译openwrt固件
- 学习c语言的第14天
- Matlab之rand(), randn(), randi()函数的使用方法