Bình luận

• 
  

  1

  

  ngoccaidu2008  đã bình luận lúc 17, Tháng 10, 2025, 15:36

  Gợi ý:

  gọi G là 1 trọng số bất kì có thể thỏa mãn yêu cầu của đề hoặc không thỏa mãn. Như vậy G chỉ có thể nằm trong đoạn từ [1,max(A)]

  với mỗi giá trị G thì ta xem có bao nhiêu bội số nằm trong A và gcd của các bội đó có bằng G hay không. Nếu bằng thì tăng biến đếm.

  Nói chung bài này dùng biến thể của sàng cùng với mảng đánh dấu thì AC

  code tham khảo:

  #pragma GCC optimize("O2")
  #pragma GCC target("avx,avx2,fma")
  #include <bits/stdc++.h>
  using namespace std;
  #define __Hormer_Nguyen__ signed main()
  #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
  const int maxn=5+1e5;
  int n,a[maxn],id[maxn],s[maxn],ma;
  __Hormer_Nguyen__
  {
      ios::sync_with_stdio(false);
      cin.tie(0);
      cin>>n;
      for (int i=1;i<=n;i++)
      {
          cin>>a[i];
          id[a[i]]=1;
          ma=max(ma,a[i]);
      }int cnt=0;
      for (int i=ma;i>=1;i--)
      {
          int g=0;
          for (int j=i;j<=maxn;j+=i)
          {
              if (id[j])
              {
                  if (g==0) g=j;
                  else g=__gcd(g,j);
              }
          }if (g==i) cnt++;
      }cout<<cnt;
  }
  

• 
  

  -2

  

  quangvukts  đã bình luận lúc 1, Tháng 9, 2025, 14:15

  Bài dể như v mà cho 0,20 🤣