首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >第五届蓝桥杯决赛B组C/C++——生物芯片

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

作者头像
mathor
发布2018-06-22 10:05:29
6560
发布2018-06-22 10:05:29
举报
文章被收录于专栏:mathormathor

生物芯片

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

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-04-22,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档