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

相关文章

来自专栏CSDN技术头条

编码过程中需尽量避免的 7 条捷径

1. 复制代码 “我认为最有价值的规则是避免重复。有且仅有一次是极限编程里的说法。- Martin Fowler 这很容易成为头号规则。如果你想要你的代码坚如磐...

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

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

3425
来自专栏玉树芝兰

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

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

982
来自专栏我的博客

面试和笔试汇总

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

3446
来自专栏恰同学骚年

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

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

1075
来自专栏编程

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

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

25410
来自专栏python全栈布道师

python2018.06聚会笔记

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

732
来自专栏WeTest质量开放平台团队的专栏

60帧的丝般顺畅 - QQ飞车手游优化点滴

加入项目组的这段时间主要是承担性能优化这块的工作,同时也会去实现一些场景材质、特效材质以及工具。今天就性能优化这块分享一下个人的经验。

752
来自专栏何俊林

一种支持多种流媒体协议的播放内核

1195
来自专栏Python爬虫实战

Python爬虫之六:智联招聘进阶版

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

1591

扫码关注云+社区