首页 > 其他分享 >LuoguP4318 完全平方数

LuoguP4318 完全平方数

时间:2023-06-05 18:34:13浏览次数:40  
标签:LuoguP4318 ch 乌斯 容斥 平方 完全 sqrt 莫比

标签:莫比乌斯函数,容斥

完全平方数

题目描述

小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。

这天是小X的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数,然后选取了第 K个数送给了小X。小X很开心地收下了。

然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗?

\(k \leqslant 10^9\)

思路点拨

k是比较大的,所以我们可以二分转check.怎么查询一个数 \(x\) 是第几个数,就是查询在 \(1\) 到 \(x\) 之间有多少个数没有平方因子.但是这样欧拉筛会爆掉,完全无法通过.而直接计算

\[\sum_{i=1}^{\sqrt x} \lfloor \dfrac{x}{i^2}\rfloor \]

这样答案会偏大,因为举个例子,\(2^2\) 时, \(36\) 被统计了一次, \(3^2\) 时,它又被统计了一次.所以我们需要容斥一下,而这个容斥系数显而易见的就是莫比乌斯函数 \(\mu(i)\) .

这里解释一下为什么是莫比乌斯函数?

  • 如果一个数的质因子有大于 \(1\) 的完全平方因子,这肯定会被算重.不考虑,此时莫比乌斯函数值刚好是 $0 $ .

  • 一个数的质因子数量如果是奇数,那么它要么被算多了,要么没被算到

  • 一个数的质因子数量如果是偶数,这肯定会被算重.

莫比乌斯函数的容斥天赋很高的好不好.

所以答案就是 \(\sum_{i=1}^{\sqrt x} \mu(i) \lfloor \dfrac{n}{i^2}\rfloor\) .

时空复杂度分析:时间 \(O(T \sqrt k \log k)\) , 空间 \(O(\sqrt k)\) , 要筛莫比乌斯函数.

\(code\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int MAXN=1e5+10,N=1e5;
int n,T,miu[MAXN];
bool vis[MAXN];
void prepare(){
	for(int i=1;i<=N;i++) miu[i]=1;
	for(int i=2;i<=N;i++){
		if(vis[i]) continue;
		miu[i]=-1;
		for(int j=i*2;j<=N;j+=i){
			if(j%(i*i)==0)
				miu[j]=0;
			else miu[j]*=miu[i];
			vis[j]=1;
		}
	}
} 
int f(int x){
	int cnt=0;
	for(int i=1;i*i<=x;i++)
		cnt+=miu[i]*(x/(i*i));
	return cnt;
}
int solve(int x){
	int l=1,r=1e10;
	while(l<r){
		int mid=(l+r)/2;
		if(f(mid)>=x) r=mid;
		else l=mid+1;
	}
	return l;
}
signed main(){
	prepare();
	T=read();
	while(T--){
		n=read();
		printf("%lld\n",solve(n));
	}
	return 0;
}

标签:LuoguP4318,ch,乌斯,容斥,平方,完全,sqrt,莫比
From: https://www.cnblogs.com/Diavolo/p/17458685.html

相关文章

  • Spring 3.0.5+MyBatis3.0.4整合非完全例子
    基于注解的mybatis和spring整合:[url]http://huangmin001.iteye.com/blog/1185806[/url][color=red]这个文章说的很详细,很值得一看[/color].Maven+SpringMVC+Mybatis【绝非原创,单纯整理】【四】:[url]http://playgod1984.iteye.com/blog/984113[/ur......
  • 根据层序遍历结果来构建完全二叉树
    做实习笔试时遇到的一个题里用到了根据层序遍历的结果来构建二叉树。全部代码如下importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args)throw......
  • ROS业务,IP业务完全终止
    今天,混播ROS业务完全终止,也代表着过去十三年的网络业务的完全终止。从2010年至今,这个业务给我的生活提供了物质保障,今天完全落下帷幕了。新转型的项目也有了起色。感谢ROS,感谢MIKROTIK公司的技术,给了我十几年稳定的生活。让我在逆境中度过难关。感谢拉脱维亚这个伟大的国家。接......
  • CAN 总线 MCP2551T-I/SN 收发器代替型号 DP2551-I/ST完全pin对pin兼容
    目前世界上使用最广泛的CAN收发器当属NXP(原飞利浦半导体)的各种收发器了。MCP2551是一个可容错的高速CAN器件,可作为CAN协议控制器和物理总线接口。MCP2551可为CAN协议控制器提供差分收发能力,它完全符合ISO-11898标准,包括能满足24V电压要求。它的工作速率高达1Mb/s......
  • Git入门指南:从新手到高手的完全指南
    Git是一种强大的分布式版本控制系统,广泛应用于软件开发中。它的使用不仅可以帮助开发团队更好地管理代码,还可以提高团队协作效率和代码质量。随着软件开发的不断发展,版本控制成为了程序员必备的一项技能。Git作为最流行的分布式版本控制系统,被广泛地应用于软件开发、数据分析、文......
  • Git入门指南:从新手到高手的完全指南
    Git是一种强大的分布式版本控制系统,广泛应用于软件开发中。它的使用不仅可以帮助开发团队更好地管理代码,还可以提高团队协作效率和代码质量。随着软件开发的不断发展,版本控制成为了程序员必备的一项技能。Git作为最流行的分布式版本控制系统,被广泛地应用于软件开发、数据分析、文......
  • 代码随想录算法训练营第16天 | ● 104.二叉树的最大深度 559.n叉树的最大深度 ● 111
     第六章二叉树part03 今日内容:  ●  104.二叉树的最大深度  559.n叉树的最大深度●  111.二叉树的最小深度●  222.完全二叉树的节点个数 迭代法,大家可以直接过,二刷有精力的时候 再去掌握迭代法。  详细布置   104.二叉树的最大深度 (优先掌......
  • Windows下使用Socks5代理IP的完全指南
       Socks5代理是一种常用的网络代理协议,它能够为用户提供更高的隐私保护和更广泛的应用支持。本文将详细介绍如何在Windows操作系统下使用Socks5代理IP,并提供一些实用技巧和注意事项,帮助读者更好地理解和应用代理IP技术。一、什么是Socks5代理IP?   Socks5代理是一种网络......
  • centos7上Hadoop2.7.2完全分布式部署
    1.规划node1         node2           node3datanode       datanode         datanodenamenode     resourcemanager  secondarynamenodenodemanager   nodemanager     no......
  • 完全免费的chatGPT国内镜像-目前可用
    亲测完全免费,速度快。缺点:有使用频率限制,不过可以自定义自己的Key后无任何限制地址:https://api35.pxj123.cn ......