Codeforces Round 886 (Div. 4)F. We Were Both Children（调和级数、埃氏筛）

F. We Were Both Children
题意：n只青蛙初始在0处，每只青蛙都有一个a[i]表示青蛙每次能跳a[i],我们可以在1~n的位置处放置一个陷阱，每只青蛙经过陷阱后会掉进陷阱，求最多能捕获多少只青蛙。
思路：我们观察a[i]的范围很大是1e9，但是只有n以内的数据是有效的，其他数据都是无效的，所以直接舍去，然后统计有效数字出现的次数，对于i，他会经过i * 1, i * 2, i * 3, …,我们直接去枚举这些出现过的数，然后给n范围以内的这些他们经过的数上面加上，当前i的数量，因为每次跳i步的青蛙可能不知一个
也就是说我们枚举的范围是n + n/+ n/3 + n/4 + … + 1这个复杂度就是调和级数。
代码很简单如下：

#include 
#define LL long long
#define x first
#define y second
 
using namespace std;
const int N = 2e5 + 10;
LL a[N], n;

void solve()
{
	cin >> n;
	map<int, int>mp, cnt;
	for(int i = 1; i <= n; ++ i)	
	{
		int xx; cin >> xx;
		if(xx > n)	continue;
		a[i] = xx;
		mp[xx] ++;
	}
	for(auto item : mp)
	{
		int k = item.x;
		for(int j = 1; j <= n / k; ++ j)
			cnt[j * k] += mp[k];	
	}
		
	int ans = 0;
	for(auto item : cnt)
		ans = max(item.y, ans);
	cout << ans << endl;
}

int main()
{
	int t; 
//	freopen("1.in", "r", stdin);
	cin >> t;
	while(t --)	solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41