poj 2992 Divisors 简单数论

统计出质因数的个数，然后乘一下就可以了。

但是数据量非常巨大，预处理出连续段的质因数的个数。

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn=500;int cnt[maxn][maxn];int n,m;void cal(int t,int tmp){    int tt=t;    for(int i=2;t!=1;i++)    {        while(t%i==0) cnt[tt][i]+=tmp,t/=i;    }}int main(){//    freopen("in.txt","r",stdin);    for(int i=1;i<=450;i++)    cal(i,1);    for(int k=1;k<=450;k++)    for(int i=1;i<=450;i++)    cnt[k][i]+=cnt[k-1][i];    while(scanf("%d%d",&n,&m)!=EOF)    {        long long ans=1;        for(int i=1;i<=n;i++)        ans*=cnt[n][i]-cnt[n-m][i]-cnt[m][i]+1;        cout<<ans<<endl;    }    return 0;}