Mật Ong (Q.Trị)

Tác giả:

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

Bình luận

2

khai434343 1:35 p.m. 3 Tháng 8, 2024

em dùng scratch thì chịu

1 phản hồi

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é.
4 phản hồi

5

SBD20_Caominhduc 2:16 p.m. 27 Tháng 7, 2024

Bài cho có thời gian chạy 0.8 giây.
TLE 3 test cuối

1

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

2

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

3
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é:))