题意：

求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
     
      #define N 10000001#define mod 100000007using namespace std;int cnt,p[N],phi[N];long long phifac[N];bool v[N];int main(){    phi[1]=1;    for(int i=2;i
      
       =N) break;            v[i*p[j]]=true;            if(i%p[j]) phi[i*p[j]]=phi[i]*(p[j]-1);            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 0;        ans=0;        phifac[1]=1;        for(int i=2;i<=m;i++)         if(!v[i]) phifac[i]=phifac[i-1]*(i-1)%mod;        else phifac[i]=phifac[i-1]*i%mod;        ans=phifac[m];        for(int i=m+1;i<=n;i++) ans=ans*i%mod;        printf("%lld\n",ans-1);    }}