UPC 6887 游戏

题目略

题目求的就是个$$\sum\text{轮数}$$ 所以根本不用管下面那个提示

根据题意像素数筛一样在$$[L,R]$$中选择必须选择的数，筛掉剩下的数(这些数的倍数)

记必须选择的数为$$sum$$,则令$$f[i]=sum * C(n – sum,n-i) * (i – 1)! * (n – i)!$$

则$$ans = \displaystyle\sum_{i = sum}^ni * f[i] = \displaystyle\sum_{i=sum}^nsum * C(n – sum,n-i)*i! *(n-i)$$

$$ans = \displaystyle\sum_{i=sum}^n sum * \frac{(n – sum)!}{(n – i)!(i-sum)} *i!$$

AC代码:

#include <iostream>
#include <algorithm>
#include <array>

using namespace std;
using ll = long long;
const int maxn = 1e7 + 1e2;
const int mod = 1e9 + 7;
array<int, maxn> fac, inv;
array<bool, maxn> vis;
int l, r, n;

int qpow(int x, int y) {
    int res = 1;
    for (; y; y >>= 1, x = 1ll * x * x % mod) {
        if (y & 1) res = 1ll * res * x % mod;
    }
    return res;
}

void shai() {
    fac[0] = 1;
    for (int i = 1; i <= r; ++i) {
        fac[i] = 1ll * i * fac[i - 1] % mod;
    }
    inv[r] = qpow(fac[r], mod - 2);
    for (int i = r; i; --i)inv[i - 1] = 1ll * i * inv[i] % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> l >> r;
    shai();

    int sum = 0;
    for (int i = l; i <= r; ++i) {
        if (!vis[i]) {
            ++sum;
            for (int j = i << 1; j <= r; j += i)vis[j] = true;
        }
    }
    n = r - l + 1;
    int ans = 0;
    for (int i = sum; i <= n; ++i) {
        ans = (ans + 1ll * sum * fac[n - sum] % mod * inv[i - sum] % mod * fac[i] % mod) % mod;
    }
    cout << ans << "\n";

}