Codeforces546 D.Soldier and Number Game（线性筛）

题意：

给定a，b，表示有一个数为$\frac{a!}{b!}$， 一次操作你可以选择一个它的因子x，然后将它除以x， 问最多能进行多少次操作。

数据范围：b<=a<=5e6

解法：

$设f(i)为i的质因子个数，g(i)={\sum }_{i=1}^{n}f(i)$

$那么答案为g(a)-g(b)$

$线性筛筛出f,求前缀和求出g,对询问O(1)输出即可.$

$f的递推方式：f[prime[j]\ast i]=f[i]+1，(prime[j]是prime[j]\ast i的最小质因子)$

code：

#include<bits/stdc++.h> using namespace std; #define ll long long #define PI pair<int,int> const int maxm=5e6+5; int np[maxm]; int p[maxm],c; ll f[maxm]; int n; void init(){ for(int i=2;i<maxm;i++){ if(!np[i]){ p[c++]=i; f[i]=1; } for(int j=0;j<c;j++){ if(1ll*p[j]*i>=maxm)break; np[p[j]*i]=1; f[p[j]*i]=f[i]+1; if(i%p[j]==0)break; } } for(int i=1;i<maxm;i++){ f[i]+=f[i-1]; } } signed main(){ init(); int T;scanf("%d",&T); while(T--){ int a,b;scanf("%d%d",&a,&b); printf("%lld\n",f[a]-f[b]); } return 0; }

---