题目描述
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(""); }
