Bình luận

• 
  

  2

  SPyofgame    5:12 p.m. 14 Tháng 6, 2020 ← chỉnh sửa 13 →

  ---

  Spoiler Alert

  ---

  Hint 1

  • Gọi \(check(x)\) là hàm kiểm tra xem \(x\) có thỏa mãn hay không

  Duyệt qua từng số, tăng biến đếm nếu \(check(x) = true\)

  \(Result\) = số lượng \(x \in A\) thỏa \(check(x) = true\)

  Hint 2

  • \(check(x) = true\) <=> \(divisors\_sum(x) < 2 * x\)

  Ta cần tính \(divisor\_sum(x)\) thì việc còn lại là kiểm tra \(O(1)\) khi duyệt \(O(n)\)

  Hint 3

  • Mathematics Approach:

  Có \(x = p_1 ^ {f_1} * p_2 ^ {f_2} * ... * p_k ^ {f_k}\) với \(p_i\) là thừa số nguyên tố và \(f_i\) là số mũ nguyên dương

  Có \(divisors\_sum(x) = \Sigma(unique\) \(t = p_1 ^ {f_1^{''} \leq f_1} * p_2 ^ {f_2^{''} \leq f_2} * ... * p_k ^ {f_k^{''} \leq f_k})\)

  <=> \(divisors\_sum(x) = \frac{p_1 ^ {f_1 + 1} - 1}{p_1 - 1} * \frac{p_2 ^ {f_2 + 1} - 1}{p_2 - 1} * ... * \frac{p_k ^ {f_k + 1} - 1}{p_k - 1}\)

  • Precalculation Approach:

  Gọi \(1 \leq d \leq x \leq max\)

  Để tiền xử lí thì \(\forall x\) ta tìm các ước \(d\) và tính tổng

  <=> Lần lượt tăng giá trị các bội \(x\) lên \(d\) đơn vị

  Hint 4

  • Mathematics Approach:

  Sàng nguyên tố để lấy tất cả các số nguyên tố \(p \leq max\)

  Khởi tạo $sum = $ rồi liên tục phân tích nhân tử để tách ra từng phần \(p_i ^ {f_i}\) để thực hiện tính toán

  • Precalculation Approach:

  Khởi tạo \(divisors\_sum(x) = 0\) \(\forall x \in [1..max]\)

  \(\forall x \in [1..max]\) tăng giá trị \(divisors\_sum[k * x]\) lên thêm \(x\) đơn vị (\(k \in ℕ^*\) and \(k * x \leq max\))

  ---

  Reference AC code |\(O(n)\) time + \(O(n)\) * \(O(log_2 n)\) query | \(O(n)\) auxiliary space | Online Solving, Sieve, Math

  C++

  vector<int> prime; /// mang cac so nguyen to
  vector<int> lpf;   /// lowest prime factor | lpf[x] la uoc nguyen to nho nhat cua x
  
  /// Sang nguyen to trong O(n)
  void sieve(int lim = LIM) {
      prime.assign(1, 2);
      lpf.assign(lim + 1, 2);
  
      lpf[1] = 1; /// can than lap vo han
      for (int i = 3; i <= lim; i += 2) {
          if (lpf[i] == 2) prime.pb(lpf[i] = i);
          for (int j = 0; j < sz(prime) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
              lpf[prime[j] * i] = prime[j];
      }
  }
  
  /// Tinh (x ^ n) trong O(log n)
  inline ll pw(ll x, ll n) {
      ll res = 1;
      while (n > 0) {
          if (n & 1) res = res * x;
          n >>= 1;
          x = x * x;
      }
      return res;
  }
  
  /// Kiem tra xem (x) co thoa man khong
  bool check(int x) {
      int t = x;
  
      ll sum = 1;
      while (x > 1) {
          /// p la so nguyen to, f la so mu
          int p = lpf[x], f = 0;
  
          /// chia x cho uoc nguyen to nho nhat cua x toi khi nao khong con uoc do nua
          /// <=> tach nhan tu (p ^ f) ra khoi x
          do x /= p, f++; while (p == lpf[x]);
  
          /// dung cong thuc toan hoc
          sum *= (pw(p, f + 1) - 1) / (p - 1); 
      }
  
      return sum < 2 * t;
  }
  
  /// Ham chinh
  int main()
  {
      /// Tien xu li
      sieve(5e6 + 100);
  
      /// Xu li
      int res = 0;
      for (int n = readInt(); n--; res += check[readInt()]); /// Duyet qua tung phan tu
  
      /// Xuat ket qua
      cout << res;
      return 0;
  }
  

  ---

  Reference AC code | \(O(n\) \(log_2 n)\) time + \(O(n)\) * \(O(1)\) query | \(O(n)\) auxiliary space | Online Solving, Precalculation

  C++

  int main()
  {
      /// Tien xu li: div_sum[x] = tong cac uoc duong cua x
      int lim = 5e6;
      vector<int> div_sum(lim + 1, 0);
      for (int i = 1; i <= lim; ++i)
          for (int j = i; j <= lim; j += i) /// Duyet qua cac boi cua (i)
              div_sum[j] += i;              /// Lan luot cong vao boi (i) cac uoc cua no
  
      /// Tien xu li: div_sum[x] < 2 * x <=> check[x] = true
      vector<bool> check(lim + 1);
      for (int i = 0; i <= lim; ++i)
          check[i] = (div_sum[i] < i * 2);
  
      /// Xu li
      int res = 0;
      for (int n = readInt(); n--; res += check[readInt()]); /// Duyet qua tung phan tu
  
      /// Xuat ket qua
      cout << res;
      return 0;
  }
  

6 bình luận nữa