Submit solution
Points:
400 (partial)
Time limit:
0.8s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
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
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; } } }
}
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++; }
}
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; }
Có ai có thể hướng dẫn cho mình bài này được không ạ. Mình cảm ơn!
sàng căn 3 và phép thử miller rabin nhé bạn
vâng em sẽ tìm thử, em cảm ơn ạ!
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ì ạ ;-;
https://vietcodes.github.io/algo/miller đây nè e :V
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
Em chx học các anh ơi
Tính bằng cbrt mới ac đc hả mn
Bày em với mọi người 45/50 :<<<
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 đê :"(
Để anh thêm 3 test trâu vào cho
Sinh n = 100000, các số đôi một phân biệt luôn
Bộ test ngon rồi, nhưng tiếc là kk có quyền chấm lại :"(((
Nãy giờ code sai Miller :< mất vài đấm :<<
Ghe qua
Bài đó chỉ cần duyện cbrt(A) + Rabin_Miller là xong
Kinh 1,8 MB :( Anh Hoàng hack rồi
Thì anh có xài mảng kích thước 3 chứ mấy :V
Nghe mùi đề tỉnh
thì là nó mà y đúc
=))))))))))))))