From ZRQ，很好的计数题
我们可以发现这$len=r-l+1$个数中有一些是必须被查到的，即它们不是一些数的倍数，它们的数目$imp$可以通过一次埃氏筛求出。
在一个排列中可怜查到某个位置时就不用检查了，那这个位置上一定是这个排列中第$imp$和必须被查的数，我们不妨从$imp$到$len$枚举这个这个位置$i$。那么这个位置上的数有$imp$种可能，答案乘上$imp$；前面这$i$个数中要塞上$i-imp$个不必须的数，答案乘上$C_{len-imp}^{i-imp}$；最后是这个点前后各有$(i-1)!$和$(len-i)$种排列，答案也要乘上这两个。最后答案即
$sumlimits_{i=imp}^{len}imp*C_{len-imp}^{i-imp}*(i-1)!*(len-i)!$
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1e7+70; 6 const long long mod=1e9+7; 7 long long facs[N],inv[N]; 8 long long l,r,len,imp,ans; 9 bool mark[N]; 10 long long qpow(long long x,long long k) 11 { 12 if(k==1) return x; 13 long long tmp=qpow(x,k/2); 14 return k%2?tmp*tmp%mod*x%mod:tmp*tmp%mod; 15 } 16 void prework() 17 { 18 len=r-l+1,facs[0]=inv[0]=1; 19 for(int i=1;i<=len;i++) 20 facs[i]=facs[i-1]*i%mod; 21 inv[len]=qpow(facs[len],mod-2); 22 for(int i=len-1;i;i--) 23 inv[i]=inv[i+1]*(i+1)%mod; 24 for(long long i=l;i<=r;i++) 25 if(!mark[i]) 26 { 27 imp++; 28 for(long long j=2*i;j<=r;j+=i) 29 mark[j]=true; 30 } 31 } 32 long long C(long long n,long long m) 33 { 34 return facs[n]*inv[m]%mod*inv[n-m]%mod; 35 } 36 int main () 37 { 38 scanf("%lld%lld",&l,&r),prework(); 39 for(int i=imp;i<=len;i++) 40 ans+=imp*C(len-imp,i-imp)%mod*facs[i-1]%mod*facs[len-i]%mod*i%mod,ans%=mod; 41 printf("%lld",ans); 42 return 0; 43 }