codeforces#304D546D.SoldierandNumberGame(数论+动态规划+前缀和)

题目链接&＃xff1a;

点击打开链接

题目大意&＃xff1a;

给出两个数&＃xff0c;问a!/b!的每次除以一个数&＃xff0c;最多除多少次

题目分析&＃xff1a;

dp[i]是对于i能够除的最大次数&＃xff08;质因数的总个数&＃xff0c;包括重复的质因数&＃xff09;&＃xff0c;那么dp[i] &＃61; dp[i/p]&＃43;1

然后递推一下&＃xff0c;作为预处理

然后预处理出前缀和&＃xff0c;利用前缀和求出b&＃43;1~a所有数的质因子的总数

代码如下&＃xff1a;

#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 &＃61; 2 ; i }int main ( )
{scanf ( "%d" , &t );init();while ( t-- ){scanf ( "%d%d" , &a , &b );printf ( "%I64d\n" , sum[a] - sum[b] );}
}