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)

，则：

f(i)=f(\frac{i}{g(i)})+\frac{g(i)\times(g(i)-1)}{2}\times\frac{i}{g(i)}

化简得：

f(i)=f(\frac{i}{g(i)})+\frac{i\times(g(i)-1)}{2}

我们注意到，

2\le l\le r\le 5\times 10^6

，所以我们可以做一遍质数筛，预处理出每个数的质因子，然后从

2

到

n

递推即可。

Code

CPP

#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 见祖宗。

题解：CF822D My pretty girl Noora

文章操作

CF822D My pretty girl Noora 题解

思路

Code

相关推荐

评论

题解：CF822D My pretty girl Noora