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

xiaoxiao2021-02-28  20

雪域羚羊的来访

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
转载请注明原文地址: https://www.6miu.com/read-2600180.html

最新回复(0)