题目:戳我这个题与HDUOJ 5317有异曲同工之妙
题意:题意看懂了上面的一大串英文之后其实很简单,就是给你一个正整数n,问你n有多少个质因子,不过这里n是通过a!/b!给定的,也就是说n=(a!/b!);
分析:由于这里1 ≤ b ≤ a ≤ 5 000 000,数据很大,所以简单暴力一定超时,具体看代码。
#include <iostream>
#include <cstdio>
using namespace std;
const int M = 5e6+; int t; //测试组数
int num[M] = {}; //打表,将n的质因子个数存到num[n]中
int sum[M] = {}; //sum[i]表示从num[1]到num[i]的和
void getsum( ) {
num[] = ;
num[] = ;
for( int i=; i<M; i++ ) {
if( num[i] > ) //判断i是否为素数
continue;
num[i] = ;
for( int j=; j*i<M; j++ ) {
num[j*i] = num[j] + ;
}
}
for( int i=; i<M; i++ )
sum[i] = sum[i-] + num[i];
} int main()
{
getsum();
scanf("%d", &t );
while( t-- ) {
int a, b;
scanf("%d %d", &a, &b );
printf("%d\n", sum[a] - sum[b] );
}
}