admin 管理员组文章数量: 1184232
SDUT Round #4
雪域羚羊的来访
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
本文标签： SDUT Round 4
版权声明：本文标题：SDUT Round #4 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.roclinux.cn/p/1698022481a283061.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论