[Mảng 1 Chiều Cơ Bản]. Bài 14. gcd của mảng
Xem dạng PDF
Gửi bài giải
Điểm:
1,00
Giới hạn thời gian:
1.0s
Java
2.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
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
Bình luận
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; }
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; }
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
test case 51 là gì vậy ạ em sai hoài test case này
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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];
}
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];
}
Cách 2 không full được code
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;
}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.