生物芯片
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