题目

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

解题思路

这题表面上看好像需要一步一步操作，实际上本质是看处于[L,R]之间的数字是否是平方数。

因为我们知道，一个数i一定可以分解为1*i，而题目将从2开始操作，也就是对于编号为i的光源，如果这个灯的编号是素数，那么它只在“所有编号为i的倍数的光源操作一次”时被取反，那么它，一定是亮的；同理，对任意的数字，如果能分解为为a*b的形式，一定有a,b<=i，那么“所有编号为a的倍数的光源操作一次”和“所有编号为b的倍数的光源操作一次”将互相抵消，光源仍保持原态；而只有当一个数能开方时，它的因数个数将会是奇数，又加上“1的倍数”这个操作被略过，因此平方数将被操作偶数次，维持初态，非平方数将被操作奇数次，与初态相反。最后，对亮的光源数目累加即可。

易错点

对是否是平方数的判断方法，先要将开方后的double类型赋值给int类型变量temp，如果temp的平方等于原数i，则i为平方数：

int temp = sqrt(i);
if (i==temp*temp)
	printf("yes");

代码

#include<stdio.h>
#include<math.h>

int main()
{
	long int N,L,R;//L<R<N<10^15,N表示光源数，L表示区间的左边界，R表示区间的右边界
	scanf("%ld %ld %ld",&N,&L,&R);
	long int i,temp,sum=0;
	for (i=L;i<=R;i++)
	{
	    temp = sqrt(i);
	    sum+=(temp*temp==i)?0:1;
	}
	printf("%ld",sum);
	return 0;
}

错误代码

按照传统方法，每遍历到一个因数i，就对所有倍数进行操作一次，发现运行超时（75分）

#include<stdio.h>
int light[10000001];//开始的时候所有光源都是关闭的
int main()
{
	long int N,L,R;//L<R<N<10^15,N表示光源数，L表示区间的左边界，R表示区间的右边界
	long int i,j,sum=0,start;
	scanf("%ld %ld %ld",&N,&L,&R);
	for (i=2;i<=R;i++)
	{
	    j = (L>i)?L:i;
	    while (j%i!=0){
	        j++;
	    }
	    for (j;j<=R;j+=i)
	        light[j-L] = (!light[j-L]);
	}
	for (i=0;i<(R-L+1);i++)
	    sum+=light[i];
	printf("%ld",sum);
	return 0;
}