第五届蓝桥杯决赛B组C/C++——生物芯片

生物芯片

X博士正在研究一种生物芯片,其逻辑密集度、容量都远远高于普通的半导体芯片。博士在芯片中设计了 n 个微型光源,每个光源操作一次就会改变其状态,即:点亮转为关闭,或关闭转为点亮。这些光源的编号从 1 到 n,开始的时候所有光源都是关闭的。博士计划在芯片上执行如下动作:

所有编号为2的倍数的光源操作一次,也就是把 2 4 6 8 ... 等序号光源打开

所有编号为3的倍数的光源操作一次, 也就是对 3 6 9 ... 等序号光源操作,注意此时6号光源又关闭了。

所有编号为4的倍数的光源操作一次。

.....

直到编号为 n 的倍数的光源操作一次。

X博士想知道:经过这些操作后,某个区间中的哪些光源是点亮的。

【输入格式】

3个用空格分开的整数:N L R  (L<R<N<10^15)  N表示光源数,L表示区间的左边界,R表示区间的右边界。

【输出格式】

输出1个整数,表示经过所有操作后,[L,R] 区间中有多少个光源是点亮的。

【样例】

输入:5 2 3

输出:2

输入:10 3 6

输出:3

思路:这题模拟的方法做最好理解也最简单,但是数据太大,光源数不超过10^15,根本开不出那么大的数组,所以只能找规律。

首先,题目告诉我们所有光源初始状态是关闭的,若想使其最终状态是打开的,很明显,要对每个灯泡进行奇数次操作,而操作的次数其实就是灯泡的因数个数,但是没有“所有编号为1的倍数的光源操作一次”,所以因数个数要-1。最终结论就是,如果编号为n的灯泡,有偶数个因数,那么最终这个灯泡是打开的。比方说,编号为6的灯泡,他的因数是1,2,3,6,四个因数,所以他最终是亮的状态。

其次,我们已知完全平方数有奇数个因数,比如9,因数是1,3,9。非完全平方数有偶数个因数,因为非完全平方数的因数一定是成对出现的,比方说18,18=1*18,2*9,3*6

那么问题的答案就是给定区间[L,R]的非完全平方数的个数,区间[L,R]内的完全平方数的个数用A表示,非完全平方数的个数用B表示,则B = (R-L+1)-A,(R-L+1)表示[L,R]这个区间内有多少个数字

对于给定的数R,[1,R]内的完全平方数有(int)sqrt(R),则[L,R]内的完全平方数个数A = (int)sqrt(R) - (int)sqrt(L-1),至于这里为什么是L-1,原因很简单,因为[L,R]是闭区间,L也包含在内,如果L本身就是个完全平方数,那么(int)sqrt(R)-(int)sqrt(L)就会少算一个完全平方数L。由A我们可以得出B = (R - L + 1) - (int)sqrt(R) - (int)sqrt(L-1)

#include <bits/stdc++.h>
using namespace std; 
int main()
{
	long long int n,l,r,sum;
	cin>>n>>l>>r;
	sum = r - l + 1;
	long long int ll = (int)(sqrt(l-1));//减1是为了防止刚好边界是完全平方数 
	long long int rr = (int)(sqrt(r));//[1,r]内完全的平方数个数 
	cout<<sum - (rr - ll);
	return 0;
}

其实这题跟输入的灯泡数量根本没关系,蓝桥杯数学题+1

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏BestSDK

Python 开发者提高效率的 10 个方法

Python有很多吸引程序员的功能 ,它易学,面向对象,字节码编译,免费且开源。还有运行时检查。完整快速的支持,可以执行各种任务的扩展。 高效的Python 在...

3599
来自专栏玉树芝兰

如何用Python和R对《权力的游戏》故事情节做情绪分析?

想知道一部没看过的影视剧能否符合自己口味,却又怕被剧透?没关系,我们可以用情绪分析来了解故事情节是否足够跌宕起伏。本文一步步教你如何用Python和R轻松愉快完...

1372
来自专栏Python专栏

Python | 爬虫爬取智联招聘(进阶版)

运行平台: Windows Python版本: Python3.6 IDE: Sublime Text 其他工具: Chrome浏览器

6322
来自专栏恰同学骚年

Unity3D游戏开发初探—3.初步了解U3D物理引擎

  四个世纪前,物理学家牛顿发现了万有引力,并延伸出三大牛顿定理,为之后的物理学界的发展奠定了强大的理论基础。牛顿有句话是这么说的:“如果说我看得比较远的话,那...

1375
来自专栏我的博客

面试和笔试汇总

最近忙着找工作,也没有更新博客,今天一个朋友让我赶紧把博客更新下,说说最近的面试情况也可以好给他们一个参考,这就整理出来给大家分享~~ 笔试题目公开 get和p...

4026
来自专栏GopherCoder

『Go 语言学习专栏』-- 第十三期

1992
来自专栏CDA数据分析师

深入对比数据科学工具箱:Python和R之争

概述 在真实的数据科学世界里,我们会有两个极端,一个是业务,一个是工程。偏向业务的数据科学被称为数据分析(Data Analysis),也就是A型数据科学。偏向...

2327
来自专栏峰会SaaS大佬云集

更新c++学习笔记 第一章

参加了几次笔试,发现有很多c++方面的问题被卡了。从现在开始进攻c++。之后会陆续更新c++学习笔记。

311
来自专栏GreenLeaves

Builder生成器(创建型模式)

一、使用场景: 1、假设要创建一个House设施,该设施的创建由若干个部分组成,而且这若干个部分经常变化。 如果用最直观的设计方式,每一个房屋部分的变化,都将导...

1886
来自专栏用户2442861的专栏

如何面试Python后端工程师?

http://blog.csdn.net/yueguanghaidao/article/details/49638261

1591

扫码关注云+社区