51nod 1441 欧拉筛法

题目来源: CodeForces
基准时间限制:6 秒 空间限制:131072 KB 分值: 40 难度:4级算法题
51nod 1441 欧拉筛法 收藏
51nod 1441 欧拉筛法 关注

两个士兵正在玩一个游戏,游戏开始的时候,第一个士兵为第二个士兵选一个正整数n。然后第二个士兵要玩尽可能多的轮数。每一轮要选择一个正整数x>1,且n要是x的倍数,然后用n/x去代替n。当n变成1的时候,游戏就结束了,第二个士兵所得的分数就是他玩游戏的轮数。

为了使游戏更加有趣,第一个士兵用 a! / b! 来表示n。k!表示把所有1到k的数字乘起来。

那么第二个士兵所能得到的最大分数是多少呢?

Input
单组测试数据。
第一行包含一个整数t (1 ≤ t ≤ 1,000,000),表示士兵玩游戏的次数。
接下来t行,每行包含两个整数a,b (1 ≤ b ≤ a ≤ 5,000,000)。
Output
对于每一组数据,输出第二个士兵能拿到的最多分数。
Input示例
2
3 1
6 3
Output示例
2
5
思路:
一个大于1的整数肯定有一些质数组成,由于分数要最多,也就是每次除能够整除的质数。
这样问题就转化为了,求b+1,b+2...,a之间有多少个质数。由于一个合数由质数相乘构成,所以
可以在欧拉筛的时候,处理一下每个数有多少个质数组成。在处理一下前缀和。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<time.h>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 1000000001
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN = ;
int isnotprime[MAXN],prime[MAXN],cnt;
int a,b;
int ans[MAXN];
ll sum[MAXN];
void Init()
{
cnt = ;
memset(ans,,sizeof(ans));
memset(isnotprime,,sizeof(isnotprime));
for(int i = ; i <= MAXN - ; i++){
if(!isnotprime[i]){
ans[i] = ;
prime[cnt++] = i;
}
for(int j = ; j < cnt && 1LL * i * prime[j] < MAXN; j++){
isnotprime[i*prime[j]] = ;
ans[i*prime[j]] += ans[i] + ans[prime[j]];
if(i % prime[j] == )break;
}
}
sum[] = ;
sum[] = ;
for(int i = ; i <= MAXN - ; i++){
sum[i] = sum[i-] + ans[i];
}
}
int main()
{
int t;
Init();
cin >>t;
while(t--){
scanf("%d%d",&a,&b);
cout<<sum[a] - sum[b]<<endl;
}
return ;
}
上一篇:Apache Ignite 学习笔记(一): Ignite介绍、部署安装和REST/SQL客户端使用


下一篇:UVa 455 Periodic Strings