补题 We Were Both Children

题目描述

Mihai and Slavic were looking at a group of $ n $ frogs, numbered from $ 1 $ to $ n $ , all initially located at point $ 0 $ . Frog $ i $ has a hop length of $ a_i $ .

Each second, frog $ i $ hops $ a_i $ units forward. Before any frogs start hopping, Slavic and Mihai can place exactly one trap in a coordinate in order to catch all frogs that will ever pass through the corresponding coordinate.

However, the children can’t go far away from their home so they can only place a trap in the first $ n $ points (that is, in a point with a coordinate between $ 1 $ and $ n $ ) and the children can’t place a trap in point $ 0 $ since they are scared of frogs.

Can you help Slavic and Mihai find out what is the maximum number of frogs they can catch using a trap?

输入格式

The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the number of frogs, which equals the distance Slavic and Mihai can travel to place a trap.

The second line of each test case contains $ n $ integers $ a_1, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the lengths of the hops of the corresponding frogs.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case output a single integer — the maximum number of frogs Slavic and Mihai can catch using a trap.

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
7
5
1 2 3 4 5
3
2 2 2
6
3 1 3 4 9 10
9
1 3 2 4 2 3 7 8 5
1
10
8
7 11 6 8 12 4 4 8
10
9 11 9 12 1 7 2 5 8 10

样例输出 #1

1
2
3
4
5
6
7
3
3
3
5
0
4
4

提示

In the first test case, the frogs will hop as follows:

  • Frog 1: $ 0 \to 1 \to 2 \to 3 \to \mathbf{\color{red}{4}} \to \cdots $
  • Frog 2: $ 0 \to 2 \to \mathbf{\color{red}{4}} \to 6 \to 8 \to \cdots $
  • Frog 3: $ 0 \to 3 \to 6 \to 9 \to 12 \to \cdots $
  • Frog 4: $ 0 \to \mathbf{\color{red}{4}} \to 8 \to 12 \to 16 \to \cdots $

  • Frog 5: $ 0 \to 5 \to 10 \to 15 \to 20 \to \cdots $

    Therefore, if Slavic and Mihai put a trap at coordinate $ 4 $ , they can catch three frogs: frogs 1, 2, and 4. It can be proven that they can’t catch any more frogs. In the second test case, Slavic and Mihai can put a trap at coordinate $ 2 $ and catch all three frogs instantly.

题解

题目解析

一开始想到 $O(n^2)$ 的写法, 但是显然这个数据范围并不能AC. 我们换种想法: 同一种跳跃长度如果记录了其有多少个青蛙的话只需要扫一遍, 我们只需要 $1\sim n$ 的每个跳跃长度都只扫一遍就好了. 并且扫的时候步长会慢慢变大.

事实上, 其遍历次数为:

时间复杂度就是这个了. 由数学分析我们可得 $\sum\frac{1}{k}$ 的阶和 $\ln n$ 的是相同的嘛. 可以用 $\text{stolz}$ 定理求, 我这里就不多提了.

AC代码

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
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define MOD(size) const long long MOD = size
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

MAXN(2e5);
int a[MAXN],b[MAXN];

signed main(){
	T_{
		mem(a,0);mem(b,0);
		int n;
		cin >> n;
		fa(i,1,n){
			int temp;
			cin >> temp;
			if(temp <= n) a[temp]++;//统计跳各个长度的青蛙的个数
		}
		fa(i,1,n){
			for(int j=0;j<=n;j+=i){
				b[j] += a[i];//b[j]是青蛙可以蹦到的j位置的个数,这里的j是步长慢慢变长的嘛.
			}
		}
		int ans = -0x3f3f3f3f;
		fa(i,1,n) ans = max(ans,b[i]);
		cout << ans << endl;
	}
	return 0;
}