Mật Ong (Q.Trị)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
algorit
Dạng bài
Điểm: 1800 (p) Thời gian: 0.8s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Một đàn ong mật có \(N\) con được đánh số từ \(1\) đến \(N\), con thứ \(i(1 \le i \le N)\) có trọng lượng là số nguyên \(A_i\).

Biết rằng nếu một con ong có trọng lượng \(X\) thì trong một ngày sản xuất được lượng mật là \(X * f(X)\), với \(f(X)\) là số ước dương của \(X\).

  • Yêu cầu: Hãy tính tổng lượng mật sản xuất được trong một ngày của cả đàn ong.

Input

  • Dòng đầu ghi duy nhất số nguyên dương \(N\).
  • Dòng thứ hai lần lượt \(A_1,A_2,...,A_N\), các số cách nhau ít nhất một dấu cách.

Output

  • Một số duy nhất là tổng lượng mật sản xuất được trong một ngày của cả đàn ong.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N \le 1000 , A_i \le 10^8 .\)*
  • Subtask \(2\) (\(30\%\) số điểm): \(N \le 10^5 , A_i \le 10^6 .\)*
  • Subtask \(3\) (\(20\%\) số điểm): \(N \le 10^5 , A_i \le 2.10^7 .\)*
  • Subtask \(4\) (\(20\%\) số điểm): \(N \le 10^5 , A_i \le 10^8.\)*

Example

Test 1

Input 
4
1 2 3 4
Output 
23

Bình luận


  • 20
    tester123    10:35 p.m. 2 Tháng 8, 2024 ← đã chỉnh sửa
    My solution

    Bài này có thể giải bằng sàng căn 3 và không cần dùng phép thử miller rabin

    Chúng ta cần nhớ đến tính chất của 1 số nguyên:

    1 số nguyên a có dạng phân tích ra thừa số nguyên tố là (x1 ^ y1) * (x2 ^ y2) * ... * (xn ^ yn) thì số ước của số nguyên đó là (y1 + 1) * (y2 + 1) * (y3 + 1) * ... * (yn + 1)

Ví dụ: số 12 phân tích ra thừa số nguyên tố sẽ là (2 ^ 2) * 3, số ước là (2 + 1) * (3 + 1) = 6

    Dựa vào tính chất này, ta có thê giải bài này như sau:

    B1: Lập một vector v, push_back tất cả các số nguyên tố trong khoảng từ 2 đến 10000 vào vector này.
    B2: Lập 1 hàm đếm ước p(n) như sau: đặt biến kết quả res = 1, duyệt tất cả các phần tử i trong vector v (i ở đây được coi là số nguyên tố được push_back vào mảng v chứ không phải chỉ số nhé), nếu như n chia hết cho i thì đặt biến đếm cnt = 0, dùng vòng while(n % i == 0) n /= i, cnt++. cuối cùng là nhân res với (cnt + 1). Kết quả của hàm là return res;
    B3: Lập 1 mảng f[10 ^ 7], với mỗi a[i] ta lưu p(a[i]) vào f[a[i]] để nếu như sau có số a[i] thì không phải gọi lại hàm mà có thể dùng kết quả từ mảng f. Rồi cộng hết vào biến kết quả rồi in ra là xong rồi.

    • Lưu ý, để giảm độ phức tạp, không nên dùng mảng để lưu các phần tử của mảng a, thay vào đó mỗi vòng for ta dùng int a, cin >> a rồi giải bài toán trực tiếp đồng thời với việc nhập, xuất.

    Code tham khảo (Vạn lần xin bro đừng cop mà chỉ xem khi quá bí và khi đã làm theo cách trên mà vẫn không được):
    https://ideone.com/7UaRJ4

    Nếu thấy hay thì cho tôi xin 1 upvote nhé =)))
    Đồng thời nếu có gì sai sót thì trả lời lại comment này nhé.

    • 12 bình luận nữa