BZOJ5323 JXOI2018游戏（线性筛+组合数学）

　　可以发现这个过程非常类似埃氏筛，将在该区间内没有约数的数定义为质数，那么也就是求每种方案中选完所有质数的最早时间之和。

　　于是先求出上述定义中的质数个数，线性筛即可。然后对每个最短时间求方案数，非常显然的组合数。最好特判一下l=1的情况，毕竟如果1作为质数会有奇怪的事。

　　我的线性筛……跑的几乎跟埃氏筛差不多慢。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 10000010

#define P 1000000007

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,l,r,prime[N],fac[N],inv[N],cnt,sum,ans;

bool flag[N];

int C(int n,int m){return 1ll*fac[n]*inv[n-m]%P*inv[m]%P;}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5323.in","r",stdin);

    freopen("bzoj5323.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    l=read(),r=read();n=r-l+;

    fac[]=;for (int i=;i<=n;i++) fac[i]=1ll*i*fac[i-]%P;

    inv[]=inv[]=;for (int i=;i<=n;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;

    for (int i=;i<=n;i++) inv[i]=1ll*inv[i]*inv[i-]%P;

    if (l==) sum=;

    else

    {

        for (int i=;i<l;i++)

        {

            if (!flag[i]) prime[++cnt]=i;

            for (int j=;j<=cnt&&prime[j]*i<l;j++)

            {

                flag[prime[j]*i]=;

                if (i%prime[j]==) break;

            }

        }

        sum=-cnt;

        for (int i=l;i<=r;i++)

        {

            if (!flag[i]) prime[++cnt]=i;

            for (int j=;j<=cnt&&prime[j]*i<=r;j++)

            {

                flag[prime[j]*i]=;

                if (i%prime[j]==) break;

            }

        }

        sum+=cnt;

    }

    for (int i=sum;i<=n;i++) ans=(ans+1ll*fac[n-sum]*C(i-,sum-)%P*i)%P;

    cout<<1ll*ans*fac[sum]%P;

    return ;

}