51nod 1441 士兵的数字游戏(埃氏筛)
发布日期:2021-11-02 09:48:40
浏览次数:3
分类:技术文章
本文共 1219 字,大约阅读时间需要 4 分钟。
1441 士兵的数字游戏
题目
两个士兵正在玩一个游戏,游戏开始的时候,第一个士兵为第二个士兵选一个正整数n。然后第二个士兵要玩尽可能多的轮数。每一轮要选择一个正整数x>1,且n要是x的倍数,然后用n/x去代替n。当n变成1的时候,游戏就结束了,第二个士兵所得的分数就是他玩游戏的轮数。
为了使游戏更加有趣,第一个士兵用 a! / b! 来表示n。k!表示把所有1到k的数字乘起来。
那么第二个士兵所能得到的最大分数是多少呢?
输入
单组测试数据。
第一行包含一个整数t (1 ≤ t ≤ 1,000,000),表示士兵玩游戏的次数。 接下来t行,每行包含两个整数a,b (1 ≤ b ≤ a ≤ 5,000,000)。输出
对于每一组数据,输出第二个士兵能拿到的最多分数。
输入样例
2
3 1 6 3输出样例
2
5#include#include #include using namespace std;typedef long long ll;const int maxn = 5e6 + 5;int vis[maxn];ll sum[maxn];void init_prim() { vis[0] = vis[1] = 1; sum[0] = sum[1] = 0; for (int i = 2; i < maxn; i++) { if (!vis[i]) { sum[i] = 1; for (int j = i + i; j < maxn; j += i) { vis[j] = 1; int n = j, num = 0; while (n % i == 0) { num++; n /= i; } sum[j] += num; } } } for (int i = 1; i < maxn; i++) { sum[i] += sum[i - 1]; }}int main() { init_prim(); int t; scanf("%d", &t); while (t--) { int a, b; scanf("%d%d", &a, &b); printf("%lld\n", sum[a] - sum[b]); } return 0;}
转载地址:https://blog.csdn.net/weixin_43820352/article/details/108429123 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年03月31日 15时14分39秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java线程管理利器:java.util.current的用法举例
2019-04-25
native2ascii.exe的使用
2019-04-25
docker-machine的安装
2019-04-25
用docker-machine创建虚拟主机
2019-04-25
spring mvc 4 + swagger2
2019-04-25
Jenkins之持续构建
2019-04-25
sonarqube 启动不了,异常提示:远程主机强迫关闭了一个现有的连接。
2019-04-25
jenkins 参数化构建作业
2019-04-25
容器div内容超出后,自动出现滚动条
2019-04-25
RDLC报表相关
2019-04-25
RDLC报表打印尺寸不匹配的问题
2019-04-25
Dev GridControl控件行拖拽实现
2019-04-25
GridControl分页
2019-04-25
DevExpress gridcontrol 分组显示
2019-04-25
违反并发性: UpdateCommand影响了预期 1 条记录中的 0 条
2019-04-25
C#文件相关操作
2019-04-25
C# INI文件操作
2019-04-25
Codeforces Round #726 (Div. 2)
2019-04-25
springboot 发送,简单,html格式,带本地附件,带远程附件邮件详解
2019-04-25