题解：CF822D My pretty girl Noora

porse · 2024-11-20 16:44:25 · 题解

CF822D My pretty girl Noora 题解

个人认为题意翻译已经足够清晰，于是我就不再赘述了。

思路

首先，看到筛选方法，感到很奇怪，于是我便觉得这是到找规律题，于是开始推式子。

假设按照 x 人一组淘汰，那么：

• 这一组淘汰 x 个人；
• 这一组有 \frac{x\times (x-1)}{2} 次比较。

所以平均每 \frac{\frac{x\times (x-1)}{2}}{x}=\frac{x-1}{2} 次比较淘汰一个人，显然，要使比较最少，\frac{x-1}{2} 也要尽可能小，所以 x 要尽可能小。又因为 x\,|\,m（m 的含义与题目相同） ，所以 x 应取 m 的最小质因子。

所以我们有了递推方程，设 x 的最小质因子为 g(x)，则：

化简得：

我们注意到，2\le l\le r\le 5\times 10^6，所以我们可以做一遍质数筛，预处理出每个数的质因子，然后从 2 到 n 递推即可。

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long
constexpr int maxn = 5000010, modd = 1e9 + 7;

int t, l, r, poww, ans;

int p[maxn], book[maxn], cnt;
int g[maxn]; //最小质因数
void prime() { // 质数筛
    for (int i = 2; i <= 5000000; i++) {
        if (!book[i]) {
            p[++cnt] = i;
            g[i] = i; //求最小质因数
        }
        for (int j = 1; j <= cnt && i * p[j] <= 5000000; j++) {
            book[i * p[j]] = 1;
            g[i * p[j]] = p[j]; //求最小质因数
            if (i % p[j] == 0) {
                break;
            }
        }
    }
    return ;
}

int M(int x) { //一个万能取模，非常好用，强烈推荐！！！
    return ((x < 0) ? ((x % modd + modd) % modd) : ((x < modd) ? x : x % modd));
}

int f[maxn];
void getf() { //递推
    f[1] = 0;
    for (int i = 2; i <= 5000000; i++) {
        f[i] = M(f[i / g[i]] + M(i * (g[i] - 1) / 2));
    }
    return ;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); //读入、输出优化

    cin >> t >> l >> r;

    prime();
    getf();
    poww = 1; //答案中的指数部分
    for (int i = l; i <= r; i++, poww = M(poww * t)) {
        ans = M(ans + M(poww * f[i])); //统计答案
    }

    cout << ans << '\n';

    return 0;
}

结语：十年 OI 一场空，不开 long long 见祖宗。