《CF757B Bash‘s Big Day》

题目描述

Bash 已经踏上了成为最伟大的口袋妖怪大师的旅程。为了得到他的第一个口袋妖怪，他去了 Zulu 教授的实验室。由于 Bash 是 Zulu 教授最喜欢的学生，Zulu 允许他从实验室里取出任意数量的口袋妖怪。

但是 Zulu 警告他，每个小精灵都有一个力量值，例如 k(k>1) 个小精灵在一起，它们的力量值为 s1​,s2​,…,sk​，如果 gcd(s1​,s2​,…sk​)=1（见 gcd 的定义注释），它们之间就会互相打架。

Bash 作为一个聪明的人，不希望他的口袋妖怪互相斗争。然而，他也想最大化他从实验室里带走的神奇宝贝的数量。你能帮 Bash 找出他能带走的最大数量的口袋妖怪吗？

注意：口袋妖怪不能与自己战斗。

输入格式

输入包含两行。

第一行一个整数 n(1≤n≤105)，表示实验室中的小精灵总数。

第二行 n 个用空格隔开的整数，第 i 个整数代表第 i 个小精灵的力量值 si​(1≤si​≤105)。

输出格式

一行包含一个整数，表示能拿走的小精灵数量最大值。

显示翻译

题意翻译

输入输出样例

输入 #1复制

3 2 3 4

输出 #1复制

2

输入 #2复制

5 2 3 4 6 7

输出 #2复制

3

代码实现;

#include<bits/stdc++.h> using namespace std; int n, mx; map<int,int> mp; int main () { mp.clear(); scanf("%d",&n); for(register int i=1;i<=n;++i) { int x; scanf("%d",&x); mx = max(mx, x); for(register int j=1;j<=sqrt(x);++j) { if(x%j == 0) { mp[j]++; if(x/j != j) { mp[x/j]++; } } } } int res = 1; for(register int i=2;i<=mx;++i) { res = max(res, mp[i]); } printf("%d",res); return 0*puts(""); }