本文共 971 字，大约阅读时间需要 3 分钟。
题目链接：
题目大意：
给出两个数，问a!/b!的每次除以一个数，最多除多少次
题目分析：
dp[i]是对于i能够除的最大次数（质因数的总个数，包括重复的质因数），那么dp[i] = dp[i/p]+1
然后递推一下，作为预处理
然后预处理出前缀和，利用前缀和求出b+1~a所有数的质因子的总数
代码如下：
#include#include #include #include #define MAX 5000007using namespace std;typedef long long LL;int t,a,b;int maxPrime[MAX];int num[MAX];LL sum[MAX];void init ( ){ memset ( maxPrime , -1 , sizeof ( maxPrime ) ); for ( int i = 2 ; i < MAX ; i++ ) { if ( ~maxPrime[i] ) continue; for ( int j = 1 , t =i ; t < MAX ; j++ , t += i ) maxPrime[t] = i; } num[1] = 0; for ( int i = 2 ; i < MAX ; i++ ) if ( maxPrime[i] != -1 ) num[i] = num[i/maxPrime[i]] + 1; sum[0] = 0; sum[1] = num[1]; for ( int i = 2 ; i < MAX ; i++ ) sum[i] = sum[i-1] + num[i];}int main ( ){ scanf ( "%d" , &t ); init(); while ( t-- ) { scanf ( "%d%d" , &a , &b ); printf ( "%I64d\n" , sum[a] - sum[b] ); }}
转载地址：http://ppvjn.baihongyu.com/