CodeForces 546D

Description

两个士兵在玩一个游戏,开始的时候第一个士兵选择一个数n,并把这个数交给第二个士兵,第二个士兵必须选择一个x满足x>1 且n能被x整除,然后将n变为n/x,然后把这个数交给第一个士兵,依次循环,当n等于1时,游戏结束,第二个士兵所得的分数为他执行的游戏轮数(选择x的次数)。

为了使游戏更有趣…,第一个士兵选择的n满足如下的形式 a!/b!(a>=b), a!表示a的阶乘。

第二个士兵得到的最大分数是多少?

Input

第一行包含一个整数t (1 ≤t≤ 1 000 000),表示士兵玩游戏的次数。

接下来有t行,每行两个整数a, b(1 ≤b≤a≤ 5 000 000),用来表示n(一开始第一个士兵选择的数n)。

Output

每一次游戏输出第二个士兵能够得到的最大分数。

Sample Input

2

3 1

6 3

Sample Output

2

5

质因数分解,再前缀和处理

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define max 5000005
int a[max];
int main()
{
int t,r,l,k,i,j;
while(scanf("%d",&t)!=EOF)
{
for(i=;i<max;i++)
if(!a[i])//确保质因数的倍数已经遍历过,不再重复遍历
{
for(j=i;j<max;j+=i)
{
k=j;
while(k%i==)
{
a[j]++;
k/=i;
}
}
}
for(i=;i<max;i++)
a[i]+=a[i-];
while(t--)
{
scanf("%d%d",&r,&l);
printf("%d\n",a[r]-a[l]);
}
}
return ;
}
上一篇:python高级之多进程


下一篇:hibernate Annotation 以及注解版的数据关联 4.4