UVA 11440 Help Tomisu

https://vjudge.net/problem/UVA-11440

题意：

求2——n！ 之间有多少个整数x，满足x的所有素因子都大于m

保证m<=n

x的所有素因子都大于m 等价于 x和m！互质

因为m<=n，所以n！是 m！的整数倍

所以只需要求出m！以内和m！互质的个数

答案再乘n！/ m！ 即可

关键是求phifac(i)

考虑递推

phi（n）= n*（1-1/p1）*（1-1/p2）……

如果i是质数，那么phifac（i）比 phifac（i-1）多乘一个n*（1-1/n）

否则，phifac（i）比 phifac（i-1）多乘一个n

原理同阶乘质因数分解

#include<cstdio>

#define N 10000001

#define mod 100000007

using namespace std;

int cnt,p[N],phi[N];

long long phifac[N];

bool v[N];

int main()

{

    phi[]=;

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

    {

        if(!v[i])

        {

            p[++cnt]=i;

            phi[i]=i-;

        }

        for(int j=;j<=cnt;j++)

        {

            if(i*p[j]>=N) break;

            v[i*p[j]]=true;

            if(i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-);

            else

            {

                phi[i*p[j]]=phi[i]*p[j];

                break;

            }

        }

    }

    int n,m; long long ans;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(!n) return ;

        ans=;

        phifac[]=;

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

        if(!v[i]) phifac[i]=phifac[i-]*(i-)%mod;

        else phifac[i]=phifac[i-]*i%mod;

        ans=phifac[m];

        for(int i=m+;i<=n;i++) ans=ans*i%mod;

        printf("%lld\n",ans-);

    }

}