codeforces 546D – Soldier and Number Game(素数筛选+dp)

题目链接：Soldier and Number Game

【题意】两个士兵在玩一个游戏，第一个士兵有一个数字n，然后第二个士兵选择一个能够整除n的数x(必须是整除不能有余数)，然后n = n/x;一直这样循环下去，直到n == 1，然后第二个士兵的得分是这个游戏能够持续的回合数。第一个士兵最开始取的n= a!/b!  求第二个士兵最大的得分。

【分析】表示完全没看懂题目，后来翻题解才看懂，英语太渣。由于T很大，只能先预处理再O(1)求每个(a,b)；而因为要除的次数尽量多，每次选择的除数肯定是越小越好，则发现把n分解成质因数相乘的质因数个数就是最大循环轮数。但是还有个问题需要O(1)计算出a!/b! 似乎不太可能？a!/b!就是a*(a-1)*(a-2)*(b+1);就是b+1~a的所有分解出的质因数个数和呀。前缀和解决！关于单个分解，用dp[i] = dp[i/tmp]+1（tmp是最小的整除i的素数）;

【AC CODE】857ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 5000000;
char buf[MAXN], *ps = buf,*pe = ps+1;
inline void rnext(){
	if(++ps == pe){
		pe = (ps = buf)+fread(buf,1,sizeof(buf),stdin);
	}
}
inline int in()
{
	do{
		rnext();
	}while(!isdigit(*ps) && ps != pe);
	int ans = 0;
	do{
		ans = (ans<<1)+(ans<<3)+*ps-48;
		rnext();
	}while(isdigit(*ps) && ps != pe);
	return ans;
}
int dp[MAXN+10], prime[MAXN+10];
LL sum[MAXN+10];

void getprime()
{
	for (int i = 2; i <= MAXN; i++)
	{
		if (!prime[i])prime[++prime[0]] = i;
		for (int j = 1; j <= prime[0] && prime[j] <= MAXN / i; j++)
		{
			prime[prime[j] * i] = 1;
			if (i%prime[j] == 0) break;
		}
	}
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t = in();
	getprime();
	repe(i,1,prime[0])
		dp[prime[i]] = 1;
	repe(i,4,MAXN)
	{
		int tmp = i;
		if(binary_search(prime+1,prime+1+prime[0],i)) continue;
		for(int j = 1; j <= prime[0] && prime[j] <= tmp; j++)
		{
			if(0 == tmp%prime[j])
			{
				dp[i] = dp[tmp/prime[j]]+1;
				break;
			}
		}
	}
	repe(i,1,MAXN) sum[i] = sum[i-1]+dp[i];
	while(t--)
	{
		int a = in(),b = in();
		printf("%I64d\n", sum[a]-sum[b]);
	}
	return 0;
}