首页 > 代码库 > Codeforces 757B:Bash's Big Day(分解因子+Hash)
Codeforces 757B:Bash's Big Day(分解因子+Hash)
http://codeforces.com/problemset/problem/757/B
题意:给出n个数,求一个最大的集合并且这个集合中的元素gcd的结果不等于1。
思路:一开始把素数表打出来,发现有9k+个数,不能暴力枚举。发现O(sqrt(n)*n)似乎可行,就枚举因子,然后出现过的因子就在Hash[]加1,最后枚举素数表里的元素,找出现次数最多的,因为那些数都可以映射在素数表里面。注意最少的ans是1.
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <queue> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <stack> 12 using namespace std; 13 #define INF 0x3f3f3f3f 14 #define N 100010 15 typedef long long LL; 16 int prime[N], num[N], cnt; 17 int Hash[N]; 18 19 void biao() { 20 for(int i = 2; i <= 100000; i++) { 21 int tmp = sqrt(i); bool flag = 0; 22 for(int j = 2; j <= tmp; j++) { 23 if(i % j == 0) { 24 flag = 1; break; 25 } 26 } 27 if(!flag) prime[++cnt] = i; 28 } 29 } 30 31 int main() { 32 biao(); 33 int n; 34 scanf("%d", &n); 35 for(int i = 1; i <= n; i++) { 36 scanf("%d", &num[i]); 37 Hash[num[i]]++; 38 int tmp = sqrt(num[i]); 39 for(int j = 2; j <= tmp; j++) { 40 if(num[i] % j == 0) { 41 Hash[j]++; 42 if(j != num[i] / j) Hash[num[i] / j]++; 43 } 44 } 45 } 46 int ans = 1; 47 for(int i = 1; i <= cnt; i++) { 48 if(ans < Hash[prime[i]]) { 49 ans = Hash[prime[i]]; 50 } 51 } 52 cout << ans << endl; 53 return 0; 54 }
Codeforces 757B:Bash's Big Day(分解因子+Hash)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。