CodeForces 546D(질량 계수 표기법)
3530 단어 시계를 맞추다
To make the game more interesting, first soldier chooses n of form a! / b! for some positive integer a and b (a ≥ b). Here by k! we denote the factorial of k that is defined as a product of all positive integers not large than k.
What is the maximum possible score of the second soldier?
Input First line of input consists of single integer t (1 ≤ t ≤ 1 000 000) denoting number of games soldiers play.
Then follow t lines, each contains pair of integers a and b (1 ≤ b ≤ a ≤ 5 000 000) defining the value of n for a game.
Output For each game output a maximum score that the second soldier can get.
Sample Input Input 2 3 1 6 3 Output 2 5
**제목: **a!/b! 뒤에 있는 숫자를 최대 몇 개까지 빼야 1에 도달할 수 있느냐고 물었을 때 상질인자로 표를 쳐야 한다~~~, 접두사와
#include
#include
#define M 5000050
#define LL long long
bool isprime[M];
LL num[M];
void bymeter()
{
memset(num, 0, sizeof(num));
memset(isprime, true, sizeof(isprime));
isprime[1] = false;
for(int i=2; i//
{
if(isprime[i])
{
for(int j=i; jint temp = j;
while(temp % i == 0)
{
temp /= i;
num[j]++;
}
isprime[j] = false;
}
}
}
for(int i=1; i//
{
num[i] += num[i-1];
}
}
int main()
{
int t, a, b;
scanf("%d", &t);
bymeter();
while(t--)
{
scanf("%d%d", &a, &b);
printf("%lld
", num[a] - num[b]);
}
return 0;
}