Bình luận

• 
  

  5

  SPyofgame    8:09 a.m. 20 Tháng 6, 2020 ← chỉnh sửa 2 →

  ---

  Spoiler Alert

  ---

  Hint 1

  • Với mỗi truy vấn: Duyệt trâu tính \(\Sigma_{x = l}^{r}(\ D(x) \ )\)

  Ta cần tính \(res = \Sigma_{x = l}^{r}(\ \ \Sigma_{d\ |\ x}^{d \in N}(1) \ \ )\)

  Có nghĩa là ta tính tổng các giá trị \(D(x)\) với mọi \(x \in [l, r]\)

  ---

  Reference TLE code | \(O(q \times max\_r \times max\_r)\) time | \(O(1)\) auxiliary space | Brute-forces

  C++

  int query()
  {
      int l, r;
      cin >> l >> r;
  
      ll res = 0;
      for (int x = l; x <= r; ++x)
          for (int d = 1; d <= x; ++d) 
              sum += (x % d == 0);
  
      return res;
  }
  

  Hint 2

  • Tiền xử lí trước \(D(x) = Sigma_{d\ |\ x}^{d \in N}(d)\) với mọi \(x \in [1, max\_r]\)

  Giờ ta chỉ cần duyệt qua \(x \in [l, r]\) và tăng \(res += D(x)\) và \(D(x)\) đã được tính nên mất \(O(1)\)

  ---

  Reference AC code | \(O(max\_r \times max\_r)\) time + \(O(q) \times O(max\_r)\) query | \(O(n)\) auxiliary space | Brute-forces, Precalculation

  C++

  vector<int> divcnt; /// divisors_count
  void precalculation(int lim = 1e6 + 500) {
      divcnt.assign(lim + 1, 0);
      for (int x = 1; x <= lim; ++x)
          for (int d = 1; d <= x; ++d) 
              divcnt[x] += (x % d == 0);
  }
  
  int query()
  {
      int l, r;
      cin >> l >> r;
  
      ll res = 0;
      for (int x = l; x <= r; ++x)
          res += divcnt[x];
  
      return res;
  }
  

  Hint 3

  • Khi \((a | n)\) ta có \(n = a * b\) với \((a \leq b)\) và \((a, b \in Z)\)

  Dễ chứng minh được \(1 \leq a \leq \sqrt n \leq b \leq n\)

  Với mỗi ước \(d\) của \(x\) ta cũng có \(\frac{x}{d}\) cũng là ước của \(x\)

  Từ đó ta chỉ cần duyệt đến \(\sqrt n\) và tăng biến đếm 2 lần khi \((a \neq b)\)

  Reference AC code | \(O(max\_r \times \sqrt{max\_r})\) time + \(O(q) \times O(max\_r)\) query | \(O(n)\) auxiliary space | Brute-forces, Precalculation

  C++

  vector<int> divcnt; /// divisors_count
  void precalculation(int lim = 1e6 + 500) {
      divcnt.assign(lim + 1, 0);
      for (int x = 1; x <= lim; ++x)
      {
          int sqrtx = sqrt(x);
          for (int d = 1; d <= sqrtx; ++d) 
              if (x % d == 0)
                  divcnt[x] += 1 + (d != x / d);
      }
  }
  

  Hint 4

  • Ta cũng có thể tiền xử lí kết quả của từng đoạn \([l, r]\)

  Tuy nhiên việc này sẽ tốn thời gian lâu (2 vòng lặp \(max\_r\) cho từng cặp \([l, r] \in [1, max\_r]\))

  Nhận xét rằng: \(D(l) + ... + D(r) = (D(1) + ... + D(r)) - (D(1) + ... + D(l - 1))\)

  Gọi \(f(n) = D(1) + ... + D(n)\) hay \(f(n) = D(n) + f(n - 1)\)

  Ta có thể tiền xử lí giá trị các đoạn \([l, r] = f(r) - f(l - 1)\) trong \(O(max\_r)\)

  Reference AC code | \(O(max\_r \times \sqrt{max\_r})\) time + \(O(q) \times O(1)\) query | \(O(n)\) auxiliary space | Brute-forces, Precalculation, Partial-sum

  C++

  vector<int> divcnt; /// divisors_count
  vector<ll>  pfs;    /// prefixsum
  void precalculation(int lim = 1e6 + 500) {
      divcnt.assign(lim + 1, 0);    
         pfs.assign(lim + 1, 0);
  
      for (int x = 1; x <= lim; ++x)
      {
          int sqrtx = sqrt(x);
          for (int d = 1; d <= sqrtx; ++d) 
              if (x % d == 0)
                  divcnt[x] += 1 + (d != x / d);
  
          pfs[x] = divcnt[x] + pfs[x - 1];
      }
  }
  
  int query()
  {
      int l, r;
      cin >> l >> r;
      return pfs[r] - pfs[l - 1];
  }
  

  Hint 5

  • Đảo nhãn: Tìm ước ta cần kiểm tra tính chia hết nhưng tìm bội thì không !

  Thay vì tìm mọi ước \(d\) của \(x\) ta sẽ tăng giá trị các bội \(x\) của \(d\) lên 1

  ---

  Reference AC code | \(O(max\_r \times \log_2(max\_r))\) time + \(O(q) \times O(1)\) query | \(O(n)\) auxiliary space | Brute-forces, Precalculation, Partial-sum

  C++

  vector<int> divcnt; /// divisors_count
  vector<ll>  pfs;    /// prefixsum
  void precalculation(int lim = 1e6 + 500) {
      divcnt.assign(lim + 1, 0);
         pfs.assign(lim + 1, 0);
  
      for (int d = 1; d <= lim; ++d) {
          for (int x = d; x <= lim; x += d)
              divcnt[x]++;
  
          pfs[d] = divcnt[d] + pfs[d - 1];
      }
  }
  
  int query()
  {
      int l = readInt();
      int r = readInt();
      return pfs[r] - pfs[l - 1];
  }
  

5 bình luận nữa