Mật Ong (Q.Trị)

Xem PDF

Đ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


  • 0
    hien18086 3:39 p.m. 14 Tháng 3, 2024 đã chỉnh sửa

    sàng nt bth là ac nhé =))


    • 0
      thienbao1602 8:35 p.m. 23 Tháng 1, 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=i
      i; 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 (tmp
      tmp == 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 5:50 p.m. 11 Tháng 11, 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 phản hồi

        • 2
          VoBaThongL921 5:35 p.m. 24 Tháng 10, 2021 chỉnh sửa 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 7:26 a.m. 1 Tháng 9, 2021

            Em chx học các anh ơi


            • 1
              duyanhloveav 7:26 a.m. 1 Tháng 9, 2021

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

              1 phản hồi

              • 0
                codedao 10:05 p.m. 18 Tháng 10, 2020

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


                • 1
                  algorit 2:15 p.m. 16 Tháng 10, 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 phản hồi

                  • 3
                    hhoangcpascal 8:52 p.m. 15 Tháng 10, 2020

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

                    1 phản hồi

                    • 1
                      bin9638 5:52 p.m. 15 Tháng 10, 2020

                      Nghe mùi đề tỉnh

                      2 phản hồi