CSES - Common Divisors | Ước chung
Xem PDF
Điểm:
1500
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho một mảng gồm \(n\) số nguyên dương. Việc của bạn là tìm hai số nguyên sao cho ước chung lớn nhất của chúng càng lớn càng tốt.
Input
- Dòng đầu tiên là một số nguyên \(n:\) kích thước của mảng.
- Dòng thứ hai chứa \(n\) số nguyên \(x_1,x_2,...,x_n\): các phần tử của mảng.
Output
- In ra ước chung lớn nhất tối đa.
Constraints
- \(2 \le n \le 2 \cdot 10^5\)
- \(1 \le x_i \le 10^6\)
Example
Sample input
5
3 14 15 7 9
Sample output
7
Bình luận
include <bits/stdc++.h>
define ll long long
define str string
using namespace std;
ll n, a[1000005], k, maxs, d[1000005];
int main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
maxs = max(maxs, a[i]);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= sqrt(a[i]); j++)
{
if (a[i] % j == 0)
{
d[j]++;
if (j * j != a[i])
d[a[i] / j]++;
}
}
}
for (int i = maxs; i >= 1; i++)
{
cout << d[i] << " ";
}
return 0;
for (int i = maxs; i >= 1; i--)
{
if (d[i] >= 2)
{
cout << i;
return 0;
}
}
}
hello
include<bits/stdc++.h>
using namespace std;
long long a[10000006],f[10000006],n,d2,minx=2e9,k,l,vt,d,t,kq,maxx;
unordered_map<int,int>m;
int main()
{
freopen("vd.inp","r",stdin);
freopen("vd.out","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
m[a[i]]++;
}
maxx=*max_element(a+1,a+n+1);
for(int i=maxx;i>=1;i--)
{
k=0;
for(int j=i;j<=maxx;j+=i)
{
k+=m[j];
if(k>=2)
{
cout<<i<<"\n";
return 0;
}
}
.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.