Thừa số nguyên tố (HSG'20)

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Hãy loại một phần tử bất kỳ trong dãy số và đặt \(P\) tích các số còn lại. Phân tích thừa số nguyên tố của \(P\), sau đó tính tổng các số mũ trong thừa số nguyên tố đó. Hãy tìm cách bỏ loại bỏ số nào để tổng các số mũ nhỏ nhất có thể.

Ví dụ: cho dãy số gồm \(4\) số \(1; 2; 4; 10\). có 2 cách bỏ đều cho tổng số mũ bằng \(3\) là nhỏ nhất:

  • Cách 1: Loại bỏ số \(4\), ta có \(P=1 * 2*10=20=2^2*5\) có tổng số mũ bẳng \(3\)
  • Cách 2: Loại bỏ số \(10,\) ta có \(P=1 * 2*4=8=2^3\) có tổng số mũ bẳng \(3\)

Yêu cầu: Cho dãy số \(A\), hãy in ra tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Input

  • Đọc từ file văn bản TSNT.INP:
  • Dòng đầu tiên chứa dãy số \(n\ (n≤10^5)\).
  • Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\ (A_i≤10^6)\).

Output

  • Ghi ra file văn bản TSNT.OUT một số nguyên là tổng số mũ nhỏ nhất của phân tích thừa số sau khi bỏ một phần tử.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N≤10^4\)\(A_i≤3\).
  • Subtask \(2\) (\(30\%\) số điểm): \(N≤10^4\)\(A_i≤8\).
  • Subtask \(3\) (\(30\%\) số điểm): \(N≤10^4\)\(A_i≤10^6\).
  • Subtask \(4\) (\(10\%\) số điểm): trường hợp còn lại.

Example

Test 1

Input
4
1 2 4 10 
Output
3

Bình luận


  • 0
    SPyofgame 2:06 a.m. 19 Tháng 6, 2020

    Updated Editorial


    • -2
      algorit 11:08 p.m. 18 Tháng 6, 2020
      int slove_2(int x)
      {
          int cnt = 0;
          for (int i=2; i*i<=x; i++)
              while (x % i == 0)
              {
                  x /= i;
                  cnt++;
              }
          if (x > 1) cnt++;
          return cnt;
      }
      

      • 0
        algorit 11:06 p.m. 18 Tháng 6, 2020 chỉnh sửa 2

        int slove_2(int x)
        {
        int cnt = 0;
        for (int i=2; i
        i<=x; i++)
        while (x % i == 0)
        {
        x /= i;
        cnt++;
        }
        if (x > 1) cnt++;
        return cnt;
        }
        *


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