CSES - Common Divisors

View as PDF
All submissions
Best submissions
Authors:
Flower_On_Stone , Elektrikar
Problem types
Points: 1500 Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

You are given an array of \(n\) positive integers. Your task is to find two integers such that their greatest common divisor is as large as possible.

Input

  • The first input line has an integer \(n\): the size of the array.
  • The second line has \(n\) integers \(x_1,x_2,…,x_n\): the contents of the array.

Output

  • Print the maximum greatest common divisor.

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

Comments

  • phonglefanreal • 3:44 p.m. 20 mar, 2025 •


    0
    Reply
    • tantaidepzai • 7:31 p.m. 5 feb, 2025 • ← edit 10

      Nhớ thêm dấu # tui ko biết thêm vào hihi

      include<bits/stdc++.h>

      using namespace std;
      long long a[10000006];
      unordered_map<int, int> m;
      int main()
      {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int n;
      cin >> n;
      for (int i = 0; i < n; i++) {
      cin >> a[i];
      m[a[i]]++;
      }
      int maxx = *max_element(a, a + n);
      for (int i = maxx; i >= 1; i--) {
      int count = 0;
      for (int j = i; j <= maxx; j += i) {
      count += m[j];
      if (count >= 2) {
      cout << i << "\n";
      return 0;
      }
      }
      }
      return 0;
      }
      sigma boy , sigma boy , sigma boy , sigma boy
      skibidi toilet , skibidi toilet , skibidi toilet ,

      -1
      Reply
      • Khang1234_1234 • 3:56 p.m. 17 dec, 2024 •

        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;
        }
        }
        }

        -1
        Reply
        • ducanhkingofcoder • 3:38 p.m. 17 dec, 2024 •

          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;
          }

              }
}

          }

          -2
          Reply
          • tienthanh1602ltqb • 10:02 a.m. 7 aug, 2024 •

            .

            -2
            Reply
            • N7hoatt • 9:21 a.m. 30 aug, 2023 • ← edited

              This comment is hidden due to too much negative feedback. Click here to view it.

              -32
              Reply