Mật Ong (Q.Trị)

View as PDF
Submit solution
Points: 400 (partial)
Time limit: 0.8s
Memory limit: 1G
Input: stdin
Output: stdout
Author:
algorit
Problem types

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.

  • Sample input:

    4
1 2 3 4
  • Sample output: 
    23
  • Ràng buộc:
    • 30% số điểm tương ứng với : ~N \le 1000 , A_i \le 10^8 .~
    • 30% số điểm tương ứng với : ~N \le 10^5 , A_i \le 10^6 .~
    • 20% số điểm tương ứng với : ~N \le 10^5 , A_i \le 2.10^7 .~
    • 20% số điểm tương ứng với : ~N \le 10^5 , A_i \le 10^8.~
  • Nguồn : Đề thi HSG 2020 tỉnh Quảng Trị
View comments (22)

Comments


  • 0
    thienbao1602  commented on 8:35 p.m. 23 jan, 2022

    mọi người cho em hỏi bài này em sàng căn 3+miller_rabin những vẫn không acp được ạ. Đây là code của em:

    include <bits/stdc++.h>

    define N (int)(1e6+5)

    define ll long long

    using namespace std;

    int n, m, p[1005]; ll ans, a[N]; bool isPrime[1005] = {false};

    void sieve() { for (int i=2; ii<=1000; i++) { if (!isPrime[i]) { for (int j=ii; j<=1000; j+=i) { isPrime[j] = true; } } }

    m = 0;
for (int i=2; i<=1000; i++)
{
    if (!isPrime[i]) p[++m] = i;
}

    }

    ll mul(ll a, ll b, ll mod) { ll res = 0; while (b) { if (b&1) res = (res+a)%mod; a = (2*a)%mod; b >>= 1; } return res; }

    ll power(ll a, ll b, ll mod) { ll res = 1; while (b) { if (b & 1) res = mul(res, a, mod); a = mul(a, a, mod); b >>= 1; } return res; }

    bool check_composite(ll n, ll a, ll d, int s) { ll x = power(a, d, n); if (x == 1 || x == n-1) return false; for (int r=1; r<s; r++) { x = mul(x, x, n); if (x == n-1) return false; } return true; }

    bool miller_rabin(ll n) { if (n < 4) return (n == 2 || n == 3); int s = 0; ll d = n-1; while ((d&1) == 0) { d >>= 1; s++; }

    vector<int> v = {2, 7, 61};
for (int a : v)
{
    if (n == a) return true;
    if (check_composite(n, a, d, s)) return false;
}
return true;

    }

    ll cnt(ll x) { ans = 1; for (int i=1; i<=m; i++) { if (p[i]p[i]p[i] > x) break; int cnt = 1; while (x % p[i] == 0) { x /= p[i]; cnt++; } ans = cnt; } ll tmp = sqrt(x); if (miller_rabin(x)) ans = 2; else if (tmptmp == x && miller_rabin(tmp)) ans = 3; else if (x != 1) ans *= 4; return ans; }

    void init() { cin >> n; for (int i=1; i<=n; i++) cin >> a[i]; }

    void solve() { ll res = 0; for (int i=1; i<=n; i++) { res += a[i]*cnt(a[i]); } cout << res; }

    int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); sieve(); init(); solve(); return 0; }


  • 1
    MACHINE  commented on 5:50 p.m. 11 nov, 2021

    Có ai có thể hướng dẫn cho mình bài này được không ạ. Mình cảm ơn!


    • 1
      longkold00  commented on 11:24 p.m. 11 nov, 2021

      sàng căn 3 và phép thử miller rabin nhé bạn


      • 0
        MACHINE  commented on 8:09 a.m. 12 nov, 2021

        vâng em sẽ tìm thử, em cảm ơn ạ!


      • 1
        VoBaThongL921  commented on 8:01 a.m. 12 nov, 2021

        miller rabin đếm số ước hoạt động như thế nào vậy ạ ? em xem code anh mà không biết miller rabin kiểu gì ạ ;-;


  • 2
    VoBaThongL921  commented on 5:35 p.m. 24 oct, 2021 ← edit 3

    gợi ý cho bạn nào ~không~ cần là mình tạo 1 cái sàng nguyên tố vjp pro max để tính số ước của từng số trong mảng nhé:) mé bài này mình làm từ hồi mới học c++ đến giờ mới ac được

    • dùng miller rabin nhanh hơn nhé:))

  • 0
    duyanhloveav  commented on 7:26 a.m. 1 sep, 2021

    Em chx học các anh ơi


  • 0
    duyanhloveav  commented on 7:26 a.m. 1 sep, 2021

    Tính bằng cbrt mới ac đc hả mn


  • 0
    codedao  commented on 10:05 p.m. 18 oct, 2020

    Bày em với mọi người 45/50 :<<<


  • 1
    algorit  commented on 2:15 p.m. 16 oct, 2020

    Bài này test còn yếu nên mọi người thông cảm :"(

    3 test cuối hơi có vấn đê :"(


    • 2
      hhoangcpascal  commented on 5:41 p.m. 16 oct, 2020

      Để anh thêm 3 test trâu vào cho


    • 2
      hhoangcpascal  commented on 5:31 p.m. 16 oct, 2020

      Sinh n = 100000, các số đôi một phân biệt luôn


      • 1
        algorit  commented on 12:30 a.m. 17 oct, 2020

        Bộ test ngon rồi, nhưng tiếc là kk có quyền chấm lại :"(((


  • 3
    hhoangcpascal  commented on 8:52 p.m. 15 oct, 2020

    Nãy giờ code sai Miller :< mất vài đấm :<<


    • 2
      algorit  commented on 9:22 p.m. 15 oct, 2020 ← edited

      Ghe qua


      • 2
        hhoangcpascal  commented on 9:23 p.m. 15 oct, 2020

        Bài đó chỉ cần duyện cbrt(A) + Rabin_Miller là xong


        • 3
          BichSonNhat  commented on 9:53 p.m. 15 oct, 2020

          Kinh 1,8 MB :( Anh Hoàng hack rồi


          • 3
            hhoangcpascal  commented on 10:03 p.m. 15 oct, 2020

            Thì anh có xài mảng kích thước 3 chứ mấy :V


  • 2
    bin9638  commented on 5:52 p.m. 15 oct, 2020

    Nghe mùi đề tỉnh


    • 2
      TCA_Khoa  commented on 7:21 p.m. 16 oct, 2020

      thì là nó mà y đúc


    • 2
      algorit  commented on 8:11 p.m. 15 oct, 2020

      =))))))))))))))