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

相关文章

来自专栏mathor

第一章 计算机系统概述

 现代计算机都是冯诺依曼计算机,共由五大件组成:运算器、存储器、控制器,输入设备、输出设备

431
来自专栏码匠的流水账

聊聊kafka的partition分配

本文主要研究一下kafka的partition分配,主要是key到parition的映射,partition对consumer的分配,以及partition的r...

671
来自专栏知识分享

STM32 中 BIT_BAND(位段/位带)和别名区使用入门(转载)

一、 什么是位段和别名区 是这样的,记得MCS51吗? MCS51就是有位操作,以一位(BIT)为数据对象的操作,MCS51可以简单的将P1口的第2位独立操作:...

3309
来自专栏码匠的流水账

bloomfilter的简单实现

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的,可以用于检索一个元素是否在一个集合中。

381
来自专栏海天一树

2017年第二十三届NOIP(C语言)普及组初赛试题及详细答案

竞赛时间: 2017 年 10月14日 14:30~ 16:30 选手注意:不得使用任何电子设备(如计算器、手机、电子词典等 )或查阅任何书籍资料

7571
来自专栏我是业余自学C/C++的

栈(stack)是一种特殊的线性表,其插入(也称入栈或压栈)和删除(也称出栈或弹栈)操作都在表的同一端进行。这一端被称为栈顶(top)另一端称为栈底端(bott...

591
来自专栏北京马哥教育

教程 | 比Python快100倍,利用spaCy和Cython实现高速NLP项目

相关 Jupyter Notebook 地址:https://github.com/huggingface/100-times-faster-nlp

390
来自专栏程序生活

图的广度优先搜索和深度优先搜索(邻接链表表示)邻接链表广度优先搜索深度优先搜索运行结果

邻接链表 邻接表表示法将图以邻接表(adjacency lists)的形式存储在计算机中。所谓图的邻接表,也就是图的所有节点的邻接表的集合;而对每个节点,它...

3964
来自专栏calmound

强连通专题

POJ 2762 Going from u to v or from v to u? 题意:判断该图的任意两点是否可达 分析:tarjan后进行缩点,缩点后再建...

2668
来自专栏Android知识点总结

Java总结IO之总集篇

字符流和字节流向来各行其事,很少有交集。 但Reader和Writer有两个奇子,名叫InputStreamReader(男)和OutputStreamWri...

1065

扫码关注云+社区