Mật Ong (Q.Trị)

Xem PDF
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


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

      • 9 bình luận nữa