Bình luận

• 
  

  2

  SPyofgame    12:35 a.m. 12 Tháng 6, 2020 ← chỉnh sửa 15 →

  ---

  Spoiler Alert

  ---

  Approach

  • Xét bài toán con, với mỗi số thì tổng số mũ là bao nhiêu

  Gọi kết quả thu được với mỗi phần tử \(A_i\) nhận vào là \(res_i\)

  Tổng giá trị cả mảng là \(\sum_{i=1}^n{res_i}\)

  Ta cần tìm giá trị nhỏ nhất, nên ta sẽ loại đi kết quả lớn nhất là \(\max\left(res_i\right)\)

  Vậy kết quả cần tìm là \(\sum_{i=1}^n{res_i} - \max\left(res_i\right)\)

  ---

  Hint 1

  • Duyệt \(\forall p\) nguyên tố \(\leq n\)

  Chia dần \(n\) cho \(p\) và tăng biến đếm

  Khi \(n = 1\) thì ngừng và xuất kết quả

  ---

  Hint 2

  • Với \(1 \leq a \leq b \leq n\) \(^{(1)}\) ta có \(n = a \times b\) \(^{(2)}\)

  \((2) \Leftrightarrow \sqrt n \times \sqrt n = a \times b\) mà từ \((1) \Leftrightarrow 1 \leq a \leq \sqrt n\leq b \leq n\)

  Từ đây rút ra nhận xét về cận trên của số nguyên tố \(p\) trong trương hợp \(n\) không phải số nguyên tố

  ---

  Hint 3

  • Ta có thể không cần kiểm tra tính nguyên tố của số \(p\)

  Thay vào đó ta duyệt từng ước \(d\) nhỏ nhất khác 1 của \(n\) và chia dần \(n\) cho \(d\) tới khi không chia được nữa thì duyệt tới ước lớn tiếp theo của \(n\) hiện tại

  Khi đó, ta chắc chắn rằng \(d\) là số nguyên tố, và khi chia \(n\) dần thì sẽ loại khỏi \(n\) các thừa số nguyên tố \(d\) đó đi. Nên ước nhỏ nhất tiếp theo của \(n\) cũng là số nguyên tố.

  ---

  Hint 4

  • Ta chỉ cần duyệt các số nguyên tố \(p\) bé hơn \(\sqrt n\)

  Từ nhận xét trên: Hợp số \(n\) có ước nguyên tố \(p \leq \sqrt n\)

  Ta có thể kiểm tra xem \(n\) có phải số nguyên tố hay không trong \(O(\sqrt n)\) và cũng có thể loại các ước nguyên tố \(p\) trong \(O(\sqrt n)\)

  ---

  Hint 5

  • Ta có thể không cần kiểm tra \(n\) có nguyên tố hay không

  Khi ta loại các ước \(p \leq \sqrt n\) nguyên tố ra khỏi \(n\) thì nếu sau quá trình đó, \(n > 1\) thì \(n\) là số nguyên tố

  Chứng minh: Vì ta loại hết các ước nguyên tố \(p \leq n\). Nên khi \(n > 1\) thì \(p = n\) chưa bị loại

  ---

  Reference AC code | \(O(n \sqrt{max\_val})\) time | \(O(\sqrt{max\_val})\) query | \(O(1)\) auxiliary space | Factorization

  C++

  int query(int n)
  {
      int res = 0;
      int sqrtn = sqrt(n);
      for (int p = 2; (p <= n) && (p <= sqrtn); ++p) /// p <= n (hien tai) va p <= sqrtn (truoc do) thi duyet tiep
      {
          while (n % p == 0) /// Trong khi n chia het cho p
          {
              n /= p;
              res++;
          }
      }
      if (n > 1) res++; /// n la so nguyen to
  
      return res;
  }
  

  Another Approach

  • Ta cũng có thể tìm ước nguyên tố nhỏ nhất của mọi số \(x \leq n\) trong \(O(n)\)

  Cải tiến sàng nguyên tố Eratosthenes

  \(lpf[x] =\) min divisor prime \(p\) of \(x\)

  ---

  Reference AC code | \(O(n \log_2{max\_val})\) time | \(O(\log_2{max\_val})\) query | \(O(n)\) auxiliary space | Online Solving, Sieve, Factorization

  C++

  vector<int> prime;
  vector<int> lpf; /// Lowest prime factor
  void sieve(int lim = LIM)
  {
      prime.assign(1, 2);
      lpf.assign(lim + 1, 2);
  
      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];
      }
  }
  
  int query(int n)
  {
      int res = 0;
      while ((n > 1) && (n % lpf[n] == 0)) res++, n /= lpf[n];
      return res;
  }
  
  int main()
  {
      ll sum = 0;
      int mx = 0;
      for (int n = readInt(); n--; )
      {
          int cnt = solve(readInt());
          mx = max(mx, cnt);
          sum += cnt;
      }
  
      cout << sum - mx;
      return 0;
  }
  

4 bình luận nữa