[Codeforces Round 886 (Div. 4)] F. We Were Both Children

---

https://codeforces.com/blog/entry/118466

Codeforces Round #886 (Div. 4) Editorial - Codeforces

 

※. ai 가 n을 넘어가면 잡을 수 없다.

(트랩은 n까지만 설치할 수 있다.)

 

※.1부터 n까지 곱을 cnt에 저장해준다.

(i의 개수가 1이라면 i * x 의 개수에도 1을 더해준다.)

(이 연산의 시간복잡도는 nlogn이다.)

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int Answer;
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			int N  = Integer.parseInt(br.readLine());
			long ans = 0;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int[] cnt = new int[N+1];
			for(int i = 0; i < N; i++) {
				int a = Integer.parseInt(st.nextToken());
				if(a <= N) cnt[a]++;
			}
			int[] mx = new int[N+1];
			for(int i = 1; i <= N; i++) {
				for(int j = i; j <= N; j += i) {
					mx[j] += cnt[i];
				}
			}
			for(int i = 1; i <= N; i++) ans = Math.max(ans, mx[i]);
			sb.append(ans).append('\n');
		}
		System.out.println(sb);
	}
}