第五届蓝桥杯决赛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 条评论
登录 后参与评论

相关文章

来自专栏python全栈布道师

python2018.06聚会笔记

这个小哥哥身穿白色T恤, 下身穿粉红色短裤, 讲起话来很幽默,而且喜欢自嘲式的谦虚.

11320
来自专栏Python专栏

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

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

1.4K20
来自专栏数据科学与人工智能

【Python环境】Python 开发者节省时间的 10 个方法

Python 是一个美丽的语言,可以激发用户对它的爱。所以如果你试图加入程序员行列,或者你有点厌倦C++,Perl,Java 和其他语言,我推荐你尝试Pytho...

26770
来自专栏BestSDK

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

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

38390
来自专栏恰童鞋骚年

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

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

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

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

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

5210
来自专栏编程

工业机器人编程教程-机器人编程运动

1、机器人的运动类型 ? 2、PTP运动 (1)PTP运动简要介绍 PTP运动示意图 ? 同步运动PTP 在一个PTP运动中,参与运动的轴中运动距离组长的被称之...

476100
来自专栏HBStream流媒体与音视频技术

借用PortAudio采集和播放音频,实现双路混音器

45350
来自专栏挖掘大数据

如何成为一名10x的数据分析师?

不知道大家以前听没听说过“10x Developer”这个词,如果你连听都还没听说过,那可真是时候考虑放弃自己的程序猿事业了。就像传说一样,一些程序猿的战斗力能...

25880
来自专栏我的博客

面试和笔试汇总

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

47160

扫码关注云+社区

领取腾讯云代金券