[Mảng 1 Chiều Cơ Bản]. Bài 14. gcd của mảng

View as PDF
Submit solution
Points: 1.00
Time limit: 1.0s
Java 2.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
28tech.com.vn
Problem source:
28Tech
Problem type
Allowed languages
C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng số nguyên A[] gồm N phần tử, tìm số lớn nhất mà mọi số trong mảng đều chia hết cho số đó.

Đầu vào

Dòng đầu tiên là số nguyên dương N

Dòng thứ 2 gồm N số nguyên viết cách nhau một vài khoảng trắng

Giới hạn

1<=N<=10^6

0<=A[i]<=10^6

Đầu ra

In ra kết quả của bài toán

Ví dụ :

Input 01
12
994626 994448 996097 995790 999692 993222 991401 999038 997163 990016 993004 990549
Output 01
1
Input 02
5
5 5 5 5 5
Output 02
5

Comments

Please read the guidelines before commenting.


  • 1
    L8_DuongThanhKhiem  commented on Nov. 14, 2025, 10:27 a.m. ← edited

    //⣿⣿⣿⣿⣿⣿⡷⣯⢿⣿⣷⣻⢯⣿⡽⣻⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣇⠸⣿⣿⣆⠹⣿⣿⢾⣟⣯⣿⣿⣿⣿⣿⣿⣽⣻⣿⣿⣿⣿⣿⣿⣿ //⣿⣿⣿⣿⣿⣿⣻⣽⡿⣿⣎⠙⣿⣞⣷⡌⢻⣟⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣿⣿⡄⠹⣿⣿⡆⠻⣿⣟⣯⡿⣽⡿⣿⣿⣿⣿⣽⡷⣯⣿⣿⣿⣿⣿⣿ //⣿⣿⣿⣿⣿⣿⣟⣷⣿⣿⣿⡀⠹⣟⣾⣟⣆⠹⣯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢠⡘⣿⣿⡄⠉⢿⣿⣽⡷⣿⣻⣿⣿⣿⣿⡝⣷⣯⢿⣿⣿⣿⣿ //⣿⣿⣿⣿⣿⣿⣯⢿⣾⢿⣿⡄⢄⠘⢿⣞⡿⣧⡈⢷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⢸⣧⠘⣿⣷⠈⣦⠙⢿⣽⣷⣻⣽⣿⣿⣿⣿⣌⢿⣯⢿⣿⣿⣿ //⣿⣿⣿⣿⣿⣿⣟⣯⣿⢿⣿⡆⢸⡷⡈⢻⡽⣷⡷⡄⠻⣽⣿⣿⡿⣿⣿⣿⣿⣿⣿⣷⣿⣿⣿⣿⣏⢰⣯⢷⠈⣿⡆⢹⢷⡌⠻⡾⢋⣱⣯⣿⣿⣿⣿⡆⢻⡿⣿⣿⣿ //⣿⣿⣿⣿⣿⣿⡎⣿⢾⡿⣿⡆⢸⣽⢻⣄⠹⣷⣟⣿⣄⠹⣟⣿⣿⣟⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⡇⢸⣯⣟⣧⠘⣷⠈⡯⠛⢀⡐⢾⣟⣷⣻⣿⣿⣿⡿⡌⢿⣻⣿⣿ //⣿⣿⣿⣿⣿⣿⣧⢸⡿⣟⣿⡇⢸⣯⣟⣮⢧⡈⢿⣞⡿⣦⠘⠏⣹⣿⣽⢿⣿⣿⣿⣿⣯⣿⣿⣿⡇⢸⣿⣿⣾⡆⠹⢀⣠⣾⣟⣷⡈⢿⣞⣯⢿⣿⣿⣿⢷⠘⣯⣿⣿ //⣿⣿⣿⣿⣿⣿⣿⡈⣿⢿⣽⡇⠘⠛⠛⠛⠓⠓⠈⠛⠛⠟⠇⢀⢿⣻⣿⣯⢿⣿⣿⣿⣷⢿⣿⣿⠁⣾⣿⣿⣿⣧⡄⠇⣹⣿⣾⣯⣿⡄⠻⣽⣯⢿⣻⣿⣿⡇⢹⣾⣿ //⣿⣿⣿⣿⣿⣿⣿⡇⢹⣿⡽⡇⢸⣿⣿⣿⣿⣿⣞⣆⠰⣶⣶⡄⢀⢻⡿⣯⣿⡽⣿⣿⣿⢯⣟⡿⢀⣿⣿⣿⣿⣿⣧⠐⣸⣿⣿⣷⣿⣿⣆⠹⣯⣿⣻⣿⣿⣿⢀⣿⢿ //⣿⣿⣿⣿⣿⣿⣿⣿⠘⣯⡿⡇⢸⣿⣿⣿⣿⣿⣿⣿⣧⡈⢿⣳⠘⡄⠻⣿⢾⣽⣟⡿⣿⢯⣿⡇⢸⣿⣿⣿⣿⣿⣿⡀⢾⣿⣿⣿⣿⣿⣿⣆⠹⣾⣷⣻⣿⡿⡇⢸⣿ //⣿⣿⣿⣿⣿⣿⣿⣿⡇⢹⣿⠇⢸⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠻⡇⢹⣆⠹⣟⣾⣽⣻⣟⣿⣽⠁⣾⣿⣿⣿⣿⣿⣿⣇⣿⣿⠿⠛⠛⠉⠙⠋⢀⠁⢘⣯⣿⣿⣧⠘⣿ //⣿⣿⣿⣿⣿⣿⣿⣿⣿⡈⣿⡃⢼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡙⠌⣿⣆⠘⣿⣞⡿⣞⡿⡞⢠⣿⣿⣿⣿⣿⡿⠛⠉⠁⢀⣀⣠⣤⣤⣶⣶⣶⡆⢻⣽⣞⡿⣷⠈⣿ //⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠘⠁⠉⠉⠉⠉⠉⠉⠉⠉⠉⠙⠛⠛⢿⣄⢻⣿⣧⠘⢯⣟⡿⣽⠁⣾⣿⣿⣿⣿⣿⡃⢀⢀⠘⠛⠿⢿⣻⣟⣯⣽⣻⣵⡀⢿⣯⣟⣿⢀⣿ //⣿⣿⣿⣟⣿⣿⣿⣿⣶⣶⡆⢀⣿⣾⣿⣾⣷⣿⣶⠿⠚⠉⢀⢀⣤⣿⣷⣿⣿⣷⡈⢿⣻⢃⣼⣿⣿⣿⣿⣻⣿⣿⣿⡶⣦⣤⣄⣀⡀⠉⠛⠛⠷⣯⣳⠈⣾⡽⣾⢀⣿ //⣿⢿⣿⣿⣻⣿⣿⣿⣿⣿⡿⠐⣿⣿⣿⣿⠿⠋⠁⢀⢀⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣌⣥⣾⡿⣿⣿⣷⣿⣿⢿⣷⣿⣿⣟⣾⣽⣳⢯⣟⣶⣦⣤⡾⣟⣦⠘⣿⢾⡁⢺ //⣿⣻⣿⣿⡷⣿⣿⣿⣿⣿⡗⣦⠸⡿⠋⠁⢀⢀⣠⣴⢿⣿⣽⣻⢽⣾⣟⣷⣿⣟⣿⣿⣿⣳⠿⣵⣧⣼⣿⣿⣿⣿⣿⣾⣿⣿⣿⣿⣿⣽⣳⣯⣿⣿⣿⣽⢀⢷⣻⠄⠘ //⣿⢷⣻⣿⣿⣷⣻⣿⣿⣿⡷⠛⣁⢀⣀⣤⣶⣿⣛⡿⣿⣮⣽⡻⣿⣮⣽⣻⢯⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⢀⢸⣿⢀⡆ //⠸⣟⣯⣿⣿⣷⢿⣽⣿⣿⣷⣿⣷⣆⠹⣿⣶⣯⠿⣿⣶⣟⣻⢿⣷⣽⣻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢀⣯⣟⢀⡇ //⣇⠹⣟⣾⣻⣿⣿⢾⡽⣿⣿⣿⣿⣿⣆⢹⣶⣿⣻⣷⣯⣟⣿⣿⣽⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢀⡿⡇⢸⡇ //⣿⣆⠹⣷⡻⣽⣿⣯⢿⣽⣻⣿⣿⣿⣿⣆⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⢸⣿⠇⣼⡇ //⡙⠾⣆⠹⣿⣦⠛⣿⢯⣷⢿⡽⣿⣿⣿⣿⣆⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠃⠎⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⢀⣿⣾⣣⡿⡇ //⣿⣷⡌⢦⠙⣿⣿⣌⠻⣽⢯⣿⣽⣻⣿⣿⣿⣧⠩⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⢰⢣⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⢀⢀⢿⣞⣷⢿⡇ //⣿⣽⣆⠹⣧⠘⣿⣿⡷⣌⠙⢷⣯⡷⣟⣿⣿⣿⣷⡀⡹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣈⠃⣸⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠟⢀⣴⡧⢀⠸⣿⡽⣿⢀ //⢻⣽⣿⡄⢻⣷⡈⢿⣿⣿⢧⢀⠙⢿⣻⡾⣽⣻⣿⣿⣄⠌⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠛⢁⣰⣾⣟⡿⢀⡄⢿⣟⣿⢀ //⡄⢿⣿⣷⢀⠹⣟⣆⠻⣿⣿⣆⢀⣀⠉⠻⣿⡽⣯⣿⣿⣷⣈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⢀⣠⠘⣯⣷⣿⡟⢀⢆⠸⣿⡟⢸ //⣷⡈⢿⣿⣇⢱⡘⢿⣷⣬⣙⠿⣧⠘⣆⢀⠈⠻⣷⣟⣾⢿⣿⣆⠹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⣠⡞⢡⣿⢀⣿⣿⣿⠇⡄⢸⡄⢻⡇⣼ //⣿⣷⡈⢿⣿⡆⢣⡀⠙⢾⣟⣿⣿⣷⡈⠂⠘⣦⡈⠿⣯⣿⢾⣿⣆⠙⠻⠿⠿⠿⠿⡿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⢋⣠⣾⡟⢠⣿⣿⢀⣿⣿⡟⢠⣿⢈⣧⠘⢠⣿ //⣿⣿⣿⣄⠻⣿⡄⢳⡄⢆⡙⠾⣽⣿⣿⣆⡀⢹⡷⣄⠙⢿⣿⡾⣿⣆⢀⡀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⢀⣀⣠⣴⡿⣯⠏⣠⣿⣿⡏⢸⣿⡿⢁⣿⣿⢀⣿⠆⢸⣿ //⣿⣿⣿⣿⣦⡙⣿⣆⢻⡌⢿⣶⢤⣉⣙⣿⣷⡀⠙⠽⠷⠄⠹⣿⣟⣿⣆⢙⣋⣤⣤⣤⣄⣀⢀⢀⢀⢀⣾⣿⣟⡷⣯⡿⢃⣼⣿⣿⣿⠇⣼⡟⣡⣿⣿⣿⢀⡿⢠⠈⣿ //⣿⣿⣿⣿⣿⣷⣮⣿⣿⣿⡌⠁⢤⣤⣤⣤⣬⣭⣴⣶⣶⣶⣆⠈⢻⣿⣿⣆⢻⣿⣿⣿⣿⣿⣿⣷⣶⣤⣌⣉⡘⠛⠻⠶⣿⣿⣿⣿⡟⣰⣫⣴⣿⣿⣿⣿⠄⣷⣿⣿⣿

    Code cho các bạn nek:

    #include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int num;
  cin >> num;

  vector<int> vec(num);
  for (int &ele : vec) {
    cin >> ele;
  }

  sort(vec.begin(), vec.end());

  cout << vec[num - 1] << ' ' << vec[num - 2];
}

  • 0
    naipret  commented on Sept. 18, 2025, 6:13 a.m. ← edited 
    #include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int num;
  cin >> num;

  vector<int> vec(num);
  for (int &ele : vec) {
    cin >> ele;
  }

  int res = 0;
  for (int ele : vec) {
    res = gcd(res, ele);
    if (res == 1) {
      break;
    }
  }

  cout << res;
}

  • 0
    panchi146  commented on July 30, 2025, 4:18 p.m.

    include <bits/stdc++.h>

    using namespace std;

int ucln(int a, int b){
    while(b){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i=0; i < n; i++) cin >> a[i];

    int res=0;
    for(int i=0; i < n; i++){
        res=ucln(a[i],res);
    }
    cout << res << endl;
    return 0;
}

  • 0
    bengokyeuanh99  commented on June 23, 2025, 5:50 p.m.

    include <cstdio>

    int gcd(int a, int b) { while (b) { int t = b; b = a % b; a = t; } return a; }

    int main() { int n, x, res; scanf("%d%d", &n, &res); for (int i = 1; i < n; ++i) { scanf("%d", &x); res = gcd(res, x); if (res == 1) break; } printf("%d\n", res); return 0; }


  • -1
    aduangzi  commented on June 23, 2025, 10:11 a.m.

    include <bits/stdc++.h>

    using namespace std; using ll = long long;

    int gcd(int a,int b) { if (b == 0) return a; else return gcd(b,a % b);
    } int main(){ iosbase::syncwith_stdio(false); cin.tie(nullptr); freopen("vao.inp","r",stdin); freopen("ra.out","w",stdout); int n; cin >> n; int a[n]; for (int i = 0; i < n; i++) cin >> a[i]; int kq = a[0]; for (int i = 1; i < n; i++) { kq = gcd(kq,a[i]); } cout << kq; return 0; }


  • -2
    EnderEggsRekt  commented on March 29, 2025, 8:20 a.m.

    include <stdio.h>

    int GCD(int a,int b){ while (b != 0){ int r=a%b; a=b; b=r; } return a;

    } int GCDofArray(int arr[],int n){ int firstelement=arr[0]; for(int i=0;i<n;i++){ firstelement=GCD(firstelement,arr[i]); if(firstelement==1){ break; } } return firstelement; } int main (){ int x; scanf("%d",&x); int a[x]; for(int i=0;i<x;i++){ scanf("%d",&a[i]); } printf("%d",GCDofArray(a,x));

    }


  • 1
    ho_sy_son_072  commented on Feb. 5, 2025, 2:06 p.m.

    include <iostream>

    include <iomanip>

    include <cmath>

    using namespace std;

    long long ucln(long long a,long long b){ long long r; while(b!=0){ r = a%b; a=b; b=r; } return a; }

    long long gcd(long long a[],int n){ long long ans = ucln(a[0],a[1]); for(int i=2;i<n;i++){ ans= ucln(ans, a[i]); } return ans; }

    int main(){
    int n; cin >> n; long long a[n]; for(int i=0;i<n;i++){ cin >> a[i]; } cout << gcd(a,n); return 0; }


  • -1
    Chu_manh_thang_cpp  commented on Dec. 2, 2024, 4:09 a.m.

    def gcd(a,b): while b != 0: a,b = b , a % b return a n = int(input()) arr = list(map(int,input().split())) ans = gcd(arr[0],arr[1]) for i in range(2,n): a = arr[i] b = arr[i - 1] GCD = gcd(a,b) if ans != GCD: ans = 1 break print(ans)


  • -2
    Dungx_2008  commented on Nov. 23, 2024, 3:03 p.m.

    include<bits/stdc++.h>

    define ll long long

    using namespace std; int main() { int n; cin >> n; vector<int> a(n); for(int i=0;i<n;i++) cin >> a[i]; ll ans = _gcd(a[0],a[1]); for(int i=2;i<n;i++) { ans = _gcd(ans,(ll)a[i]); } cout << ans; return 0; }


  • -2
    quocuy0112  commented on Nov. 8, 2024, 4:53 p.m.

    include <bits/stdc++.h>

    using namespace std;

    int gcd(long a, long b){ if (b == 0){ return a;
    } return(gcd(b, a % b)); }

    int findgcd(const vector<long> arr){ int res = arr[0]; int n = arr.size(); for (int i = 1; i < n; i++){ res = gcd(res, arr[i]); if (res == 1){ return 1; } } return res; }

    int main() { iosbase::syncwith_stdio(false); cin.tie(NULL); int n; cin >> n; vector<long> arr(n); for (int i = 0; i < n; i++){ cin >> arr[i]; } cout <<findgcd(arr); return 0; }


  • -1
    tuyen_pham  commented on Oct. 25, 2024, 1:30 p.m.

    include <bits/stdc++.h>

    using namespace std; int n,a[1000000]; int main() { cin>>n; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n);int res=0; for(int i=1;i<=a[0];i++){ if(a[0]%i==0){ int t=0; for(int j=1;j<n;j++){ if(a[j]%i!=0) break; t++; } if(t==n-1) res=max(res,i); } } cout<<res; return 0; } //full test


  • -4
    admin0506  commented on Aug. 31, 2024, 11:06 a.m.

    test case 51 là gì vậy ạ em sai hoài test case này


  • -14
    toantricker_123  commented on Aug. 7, 2024, 9:19 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -1
    Thanhall201  commented on Aug. 7, 2024, 2:45 a.m.

    Làm cách nào để không bị quá thời gian vậy mng? Mình làm 2 cách đều không được ạ.

    Cach 1

    include <iostream>

    include <math.h>

    using namespace std;

    int chiadu(int a, int b){ if(a%b==0) return 1; else return 0; }

    int main(){ int n, min=1000000+1, cnt=0, m=1; cin >> n; int a[n];

    for(int i=0; i&lt;n; i++){
    cin >> a[i];
}

for(int i=0; i&lt;n; i++){
    if(a[i]&lt;min && a[i]!=0){
        min=a[i];
    }
}

for(int i=2; i<=min; i++){
    cnt=0;
    for(int j=0; j&lt;n; j++){
        if(chiadu(a[j], i)==1) cnt++;
    }
    if(cnt==n) m=i;
}
cout << m;

    }

    Cach 2

    include <iostream>

    include <math.h>

    using namespace std;

    int gcd(int a, int b){ if(a==0) return b; while(a!=b){ if(a>b) a=a-b; else b=b-a; } return a; }

    int main(){ int n, uc=0; cin >> n; int a[n];

    for(int i=0; i&lt;n; i++){
    cin >> a[i];
}

uc=a[0];
for(int i=1; i&lt;n; i++){
    uc=gcd(uc, a[i]); 
}

cout << uc;

    }


    • -1
      Duyanhdz  commented on Oct. 30, 2024, 10:09 a.m.

      Cách 2 không full được code


    • -1
      dungcurious  commented on Sept. 13, 2024, 3:23 p.m.

      include <iostream>

      include <math.h>

      using namespace std; int main(){ int n;cin>>n; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } int somin=a[1]; for(int i=0;i<n;i++){ if(a[i]<somin) somin=a[i]; } int ketqua,dem=0; for(int i=0;i<n;i++){ if(a[i]%somin==0) dem++; else break; } if(dem==n) cout<<somin; else{ dem=0; for(int i=sqrt(somin);i>0;i--){ for(int j=0;j<n;j++){ if(a[j]%i==0){ dem++; } else{ dem=0; break; } } if(dem==n){ ketqua=i; break; } } cout<<ketqua;

      }

      }


  • -11
    bynk2311  commented on June 17, 2024, 8:46 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.