SDUT Round #4 - 2018 新春大作战 F [4158] 雪域羚羊的来访 【二分】

雪域羚羊的来访

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

雪域高原的羚羊公主来青青草原做客啦。为了表示羊村的好客之情，喜羊羊带领着羚羊公主在羊村中到处游玩。这一天，在羊村的实验室里，她了解到羊村村长慢羊羊正在研制一种特别的芯片。

村长慢羊羊在芯片中设计了 n 个微型光源，每个光源操作一次就会改变其状态，即：点亮转为关闭，或关闭转为点亮

这些光源的编号从 1 到 n，开始的时候所有光源都是关闭的。

慢羊羊村长将会在芯片上执行如下动作：

所有编号为2的倍数的光源操作一次，也就是把 2 4 6 8 … 等序号光源打开

所有编号为3的倍数的光源操作一次, 也就是对 3 6 9 … 等序号光源操作，注意此时6号光源又关闭了。

所有编号为4的倍数的光源操作一次。

…..

直到编号为 n 的倍数的光源操作一次。

羚羊公主感到村长研制的这种芯片十分的神奇，于是羚羊公主脑中产生了一个神奇的想法。现在羚羊公主想知道：经过这些操作后，某个区间中的哪些光源是点亮的。

Input

输入第一行为数据组数T（T<=20）。

每组数据仅一行，包含3个用空格分开的整数：N L R (L < R < N < 10 ^ 15) N表示光源数，L表示区间的左边界，R表示区间的右边界。

Output

输出1个整数，表示经过所有操作后，[L,R] 区间中有多少个光源是点亮的。

Sample Input

2 5 2 3 10 3 6

Sample Output

2 3

Hint

求完全平方数个数

Source

axuhongbo

题意： 略

分析： 首先我们可以自己找下规律，如果某个数是素数，除1和本身外没其他的因子，首先1的倍数不会扫过，而本身肯定扫过，所以只要是素数肯定会被扫过一次，肯定会点亮， 其他我们考虑非完全平方数，肯定有偶数个因子，除去1，就会有奇数个，所以最后就会被点亮，恰好完全平方数会有奇数个因子，除去1外，还有偶数个，所以最后不会呗点亮，我们可以预处理出来1e15内的所有平方数，然后二分判断边界即可

参考代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; vector<ll> pp; int main(){ for(int i = 1;i < 100000000;i++) { if(i*1ll*i >= 1000000000000000LL) break; pp.push_back(i*1ll*i); } int T;cin>>T; while (T--) { ll n,l,r;cin>>n>>l>>r; ll len = upper_bound(pp.begin(),pp.end(),r) - lower_bound(pp.begin(),pp.end(),l); printf("%lld\n",r - l + 1 - len); } return 0; } 如有错误或遗漏，请私聊下UP，thx