题目描述
她长大以后创业了，开了一个公司。 但是管理公司是一个很累人的活，员工们经常背着可怜偷懒，可怜需要时不时对办公室进行检查。
可怜公司有 n 个办公室，办公室编号是 l 到 l+n−1 ，可怜会事先制定一个顺序，按照这个顺序依次检查办公室。一开始的时候，所有办公室的员工都在偷懒，当她检查完编号是 i 的办公室时候，这个办公室的员工会认真工作，并且这个办公室的员工通知所有办公室编号是 i 的倍数的办公室，通知他们老板来了，让他们认真工作。因此，可怜检查完第ii 个办公室的时候，所有编号是 i 的倍数(包括 i )的办公室的员工会认真工作。
可怜发现了员工们通风报信的行为，她发现，对于每种不同的顺序 p ，都存在一个最小的 t(p) ，使得可怜按照这个顺序检查完前 t(p) 个办公室之后，所有的办公室都会开始认真工作。她把这个 t(p) 定义为 p的检查时间。
可怜想知道所有 t(p)的和。
但是这个结果可能很大，她想知道和对 109+7 取模后的结果。
输入格式
第一行输入两个整数 l,r 表示编号范围，题目中的 n就是 r−l+1 。
输出格式
一个整数，表示期望进行的轮数。
输入
2 4
输出
16
解释一下题意
个人觉得很有必要。。。
在区间([l , r]) 间选择若干个数 ， 选完一个数之后 ， 他及他的倍数都会被覆盖 ， 求所有的方案
要选多少个数才能选完的和
首先，发现有一些数是必须选的这些数的没有除他自己以外的因子 ， 所以必须选，设有sum个，
则选 i 个数结束的方案为
(huge f[i] = sum * C_{n - sum}^{n - i} * (n - i)! * (i - 1)!)
因为在第i个位置结束 ， 那么最后一个一定是必须选的数之一 ， 这个数有 sum 种可能
(huge C_{n - sum}^{n - i}) 是不选的数 ， 乘上(huge (n - i)!) 就是不选的部分的方案 ， ((i - 1)!) 就是选的那部分除了最后一个数的方案
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e7+10;
const int mod = 1e9+7;
int vis[N] , fac[N] , inv[N] , f[N];
int ksm(int a , int k)
{
int ans = 1;
for( ; k ; k >>= 1 , a = 1LL * a * a % mod)
if(k & 1) ans = 1LL * ans * a % mod;
return ans;
}
void Init(int maxn)
{
fac[0] = inv[0] = 1;
for(int i = 1 ; i <= maxn ; ++i) fac[i] = 1LL * i * fac[i-1] % mod;
inv[maxn] = ksm(fac[maxn] , mod - 2);
for(int i = maxn - 1 ; i >= 1 ; --i) inv[i] = 1LL * inv[i+1] * (i+1) % mod;
return ;
}
int C(int n , int m) { if(n < m) return 0; else return 1LL * fac[n] * inv[m] % mod * inv[n-m] % mod; }
int main()
{
int l , r;
register int i , j , sum = 0 , n , ans;
cin >> l >> r;
Init(r);
for(i = l ; i <= r ; ++i)
{
if(!vis[i])
{
sum++;
for(j = i << 1 ; j <= r ; j += i)
vis[j] = 1;
}
}
n = r - l + 1;
for(i = sum ; i <= n ; ++i)
f[i] = 1LL * sum * C(n - sum , n - i) % mod * fac[n - i] % mod * fac[i - 1] % mod;
ans = 0;
for(i = sum ; i <= r - l + 1 ; ++i) ans = (1LL * ans + 1LL * f[i] * i % mod) % mod;
cout << ans << endl;
return 0;
}