题目描述
她长大以后创业了，开了一个公司。 但是管理公司是一个很累人的活，员工们经常背着可怜偷懒，可怜需要时不时对办公室进行检查。
可怜公司有 \(n\) 个办公室，办公室编号是 \(l\) 到 \(l+n-1\) ，可怜会事先制定一个顺序，按照这个顺序依次检查办公室。一开始的时候，所有办公室的员工都在偷懒，当她检查完编号是 \(i\) 的办公室时候，这个办公室的员工会认真工作，并且这个办公室的员工通知所有办公室编号是 \(i\) 的倍数的办公室，通知他们老板来了，让他们认真工作。因此，可怜检查完第 \(i\) 个办公室的时候，所有编号是 \(i\) 的倍数(包括 \(i\) )的办公室的员工会认真工作。
可怜发现了员工们通风报信的行为，她发现，对于每种不同的顺序 \(p\) ，都存在一个最小的 \(t(p)\) ，使得可怜按照这个顺序检查完前 \(t(p)\) 个办公室之后，所有的办公室都会开始认真工作。她把这个 \(t(p)\) 定义为 \(p\) 的检查时间。
可怜想知道所有 \(t(p)\) 的和。
但是这个结果可能很大，她想知道和对 \(10^9+7\) 取模后的结果。
输入格式：
第一行输入两个整数 \(l\) , \(r\) 表示编号范围，题目中的 \(n\) 就是 \(r-l+1\) 。
输出格式：
一个整数，表示期望进行的轮数。
输入输出样例
输入样例#1：
2 4
输出样例#1：
16
\(\text{Solution:}\)
考虑到一个数能对答案有贡献，那么它一定不是其它数的倍数，假设这样的数有sum个。
对于九条可怜任意选择的排列，那么答案就是排列中最靠后的不能被其它数表示出来的数的位置。
所以我们可以枚举最靠后的那个数的位置 \(i\) ，\(i\) 位置可以选择 \(sum\) 个数中的任何一个数，而对于 \(i\) 后面的数它们是从 \(n-sum\) 个数中选出的 \(n-i\) 个数，而且可以随意排列，\(i\) 之前的数也可以随意排列，所以我们就有了一个用一堆乘法原理推出来的式子：
\[\begin{aligned} Ans=\sum_{i=sum}^{n}i \times sum \times C_{n-sum}^{n-i} \times (n-i)! \times (i-1)! \end{aligned} \]
#include#include #include #include #include #include #include #include using namespace std;#define fir first#define sec second#define pb push_back#define mp make_pair#define LL long long#define INF (0x3f3f3f3f)#define mem(a, b) memset(a, b, sizeof (a))#define debug(...) fprintf(stderr, __VA_ARGS__)#define Debug(x) cout << #x << " = " << x << endl#define travle(i, x) for (register int i = head[x]; i; i = nxt[i])#define For(i, a, b) for (register int (i) = (a); (i) <= (b); ++ (i))#define Forr(i, a, b) for (register int (i) = (a); (i) >= (b); -- (i))#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)#define ____ debug("go\n")namespace io { static char buf[1<<21], *pos = buf, *end = buf; inline char getc() { return pos == end && (end = (pos = buf) + fread(buf, 1, 1<<21, stdin), pos == end) ? EOF : *pos ++; } inline int rint() { register int x = 0, f = 1;register char c; while (!isdigit(c = getc())) if (c == '-') f = -1; while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getc())); return x * f; } inline LL rLL() { register LL x = 0, f = 1; register char c; while (!isdigit(c = getc())) if (c == '-') f = -1; while (x = (x << 1ll) + (x << 3ll) + (c ^ 48), isdigit(c = getc())); return x * f; } inline void rstr(char *str) { while (isspace(*str = getc())); while (!isspace(*++str = getc())) if (*str == EOF) break; *str = '\0'; } template inline bool chkmin(T &x, T y) { return x > y ? (x = y, 1) : 0; } template inline bool chkmax(T &x, T y) { return x < y ? (x = y, 1) : 0; } }using namespace io;const int N = 1e7 + 10, P = 1e9 + 7;int fac[N], ifac[N];int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = 1ll * a * res % P; a = 1ll * a * a % P; b >>= 1; } return res;}void init(int n) { fac[0] = 1; for (int i = 1; i <= n; ++ i) fac[i] = 1ll * fac[i - 1] * i % P; ifac[n] = qpow(fac[n], P - 2); for (int i = n - 1; i >= 0; -- i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;}int C(int n, int m) { if (n < m) return 0; return 1ll * fac[n] % P * 1ll * ifac[m] % P * 1ll * ifac[n - m] % P;}bool vis[N];int main() {#ifndef ONLINE_JUDGE file("P4562");#endif int n, L, R, sum = 0; cin >> L >> R; n = R - L + 1; init(R); for (int i = L; i <= R; ++ i) { if (!vis[i]) sum++; for (int j = i + i; j <= R; j += i) vis[j] = true; } int ans = 0; for (int i = sum; i <= n; ++ i) ans = (ans + 1ll * i * fac[i - 1] % P * sum % P * C(n - sum, n - i) % P * fac[n - i] % P) % P; cout << ans << endl;}
