求救救救救救

问题讨论区 普及段
1

题目描述

给定一个由n个正整数组成的数组，你的任务是找到两个整数，使得它们的最大公约数尽可能大。

输入格式

第一行输入一个整数n：数组的大小。第二行有n个整数x1,x2,…,xn：数组的内容。

输出格式

输出最大的最大公约数。

样例

Input 1

5 3 14 15 7 9

Output 1

7

样例解释

输入: 5 3 14 15 7 9 输出: 7 解释: 7是7和14的最大公约数。

数据范围

2 ≤ n ≤ 2 * 10^5, 1 ≤ xi ≤ 10^6

求思路，老师讲了但是找不着在哪里讲的，只好问思路了

1 个赞
2

有人在吗？？？

2 个赞
3

检查每个数 i 的倍数在数组中出现的次数，来确定是否存在至少两个数以 i 为公约数。

从大到小遍历，保证第一个满足条件的 i 就是最大的可能 GCD

2 个赞
4

@椰子糕

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int main(){
  int n;
  cin>>n;
  int maxn=0;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    maxn=max(maxn,a[i]);
  }
  for(int i=maxn;i>=1;i--){
    int sum=0;
    for(int j=1;j<=n;j++){
      if(a[j]%i==0){
        sum++;
      }
    }
    if(sum>=2){
      cout<<i;
      return 0;
    }
  }
}

TLE 58分，还有哪里要优化吗

1 个赞
5

@金杭东 @椰子糕

1 个赞
6

你这复杂度不对呀，要不在j循环里，判断,if(sum>=2) break;

1 个赞
7

加了，不对（也是58pts）

8

多少分

1 个赞
9

用老师这个方法应该咋优化（我是蒟蒻）

10

是不是可以把每个a的因数求出来。
然后用cnt数组统计一下

1 个赞
11

复杂度是 O(\displaystyle\sum_{i=1}^{n} \sqrt{a_i})

1 个赞
12

有道理[doge]

13

@椰子糕 @椰子糕 @椰子糕

14

你把统计因数的优化一下 @2345安全卫士

15

我嘞个蛋，jym归来了

16 
void f(int x){
  cnt[x]++;
  for(int i=1;i<=x/2;i++){
    if(x%i==0){
      cnt[i]++;
    }
  }
  return;
}

我就写成这样，咋改

17 
for(int j=1;j*j<=a[i];j++)//根号a[i]次循环 
    if(a[i]%j==0)//如果整除 
	{
        cnt[j]++;//因数个数桶数组++ 
        if(j*j!=a[i])//防止一样的加两遍 
        	cnt[a[i]/j]++;//a[i]/j对应的那个++ 
    }
18

输入时，b是统计a出现的次数开int b[1000001]

	for(int i=1;i<=n;i++){
		cin>>a;
		b[a]++;
        b[a]=min(b[a],2);
	}

统计时

	for(int i=1000000;i>1;i--){
		int cnt=0;
		for(int j=1;i*j<=1000000&&cnt<2;j++){
			cnt+=b[i*j];
		}
		if(cnt>=2){
			cout<<i;
			exit(0);
		}
	}
	cout<<1;
	return 0;
}
19

泥……………………

20

时间跑70ms以下，AC的

1 个赞