CodeForces 546D Soldier and Number Game 打表(求质因子个数)

  题目:戳我这个题与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] );
}
}
上一篇:js实现轮播图


下一篇:phonegap入门–2 Android phonegap工程建立