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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
Small
Dạng bài
Đ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\) và \(A_i≤3\).
  • Subtask \(2\) (\(30\%\) số điểm): \(N≤10^4\) và \(A_i≤8\).
  • Subtask \(3\) (\(30\%\) số điểm): \(N≤10^4\) và \(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
    ducanhkingofcoder    8:58 p.m. 4 Tháng 7, 2024 ← chỉnh sửa 13

    bài này các bạn muốn AC thì phải nộp mới biết đc nhé


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