首页 > 代码库 > 1179 最大的最大公约数
1179 最大的最大公约数
1179 最大的最大公约数
题目来源： SGU
基准时间限制：1 秒 空间限制：131072 KB 分值: 40
给出N个正整数，找出N个数两两之间最大公约数的最大值。例如：N = 4，4个数为：9 15 25 16，两两之间最大公约数的最大值是15同25的最大公约数5。
Input
第1行：一个数N，表示输入正整数的数量。(2 <= N <= 50000)第2 - N + 1行：每行1个数，对应输入的正整数.(1 <= S[i] <= 1000000)
Output
输出两两之间最大公约数的最大值。
Input示例
49152516
Output示例
5
思路：枚举最大公约数，然后用类似筛法的方式判断当前的约数是否在原数组中存在两个或两个以上的数是他的倍数。复杂度n*log(n);
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<math.h> 7 #include<set> 8 #include<vector> 9 #include<string.h>10 using namespace std;11 typedef long long LL;12 int ans[1000005];13 int main(void)14 {15 int n,m;16 scanf("%d",&n);17 int i,j;18 memset(ans,0,sizeof(ans));19 int t;20 int maxx = 0;21 for(i = 0; i < n; i++)22 {23 scanf("%d",&t);24 ans[t]++;25 maxx = max(maxx,t);26 }27 LL c = 0;int v ;28 for(i = maxx; i >= 1 ; i--)29 {30 v = 0;31 for(j = 1; ((LL)i*(LL)j)<= maxx ; j++)32 {33 v+=ans[i*j];34 if(v>=2)35 {36 c = i;37 break;38 }39 }40 if(c)41 break;42 }43 printf("%d\n",c);44 return 0;45 }
1179 最大的最大公约数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。