Trực nhật
Xem PDFLớp \(11\) chuyên Tin có \(n\) học sinh, thầy chủ nhiệm Linh Phan muốn chọn ra một số bạn ở lại trực nhật lớp. Để thêm tính hấp dẫn và công bằng, thầy viết một đoạn code cấp cho mỗi bạn một số tự nhiên ngẫu nhiên và quy định rằng, nếu bạn nào nhận được số có tổng các ước dương của nó nhỏ hơn hai lần số đó thì phải đi trực nhật.
Một lần không may mắn, máy tính của thầy Linh Phan đã sinh ra các số mà sau khi cấp phát cho học sinh thì không có học sinh nào phải ở lại trực nhật. Rút kinh nghiệm từ lần đó, thầy đã chuẩn bị sẵn một dãy số, rồi nhờ các em đội tuyển Tin tính xem có bao nhiêu số có tổng các ước dương nhỏ hơn hai lần số đó, nếu số lượng số này đủ nhiều thì thầy sẽ lấy dãy số đó để cấp cho các bạn trong lớp.
Yêu cầu: Cho số nguyên dương \(n\) và dãy số \(a_1\), \(a_2\),..., \(a_{n – 1}\), \(a_n\). Hãy giúp thầy Linh Phan xác định xem với dãy số này thì có bao nhiêu em học sinh phải làm nhiệm vụ trực nhật.
Input
- Dòng đầu ghi số nguyên dương \(n\), số học sinh trong lớp.
- Dòng thứ hai gồm \(n\) số nguyên dương \(a_1\), \(a_2\),..., \(a_{n–1}\), \(a_n\).
Output
- Gồm một số duy nhất là số học sinh phải ở lại trực nhật tương ứng với dãy số input.
Constraints
- \(N\leq 10^6\)
- \(a_i\leq 5.10^6\)
Scoring
- Subtask \(1\) (\(70\%\) số điểm): \(N\leq 10^3, a_i\leq 10^4\)
- Subtask \(2\) (\(15\%\) số điểm): \(N\leq 10^4, a_i\leq 5.10^6\)
- Subtask \(3\) (\(15\%\) số điểm): Không có ràng buộc gì thêm
Example
Test 1
Input
5
3 6 9 12 9 Output
3Note
- Tổng ước dương của các số là:
- Số \(3\): \(1+3=4<2.3=6\);
- Số \(6\): \(1+2+3+6=2.6=12\)
- Số \(9\): \(1+3+9=13<2.9=18\)
- Số \(12\): \(1+2+3+4+6+12=28>2.12=24\)
-
Số \(9\): \(1+3+9=13<2 * 9=18\)
-
Vậy có \(3\) số có tổng ước nhỏ hơn hai lần nó là: \(3, 9 ,9\).
Bình luận
dùng hàm để sàng số ước thì tle còn gắn vô hàm main luôn thì ac:)
-
1
longkold00
9:24 p.m. 13 Tháng 10, 2021
-
1
VoBaThongL921
9:30 p.m. 13 Tháng 10, 2021
←
đã chỉnh sửa
→
-
1
VoBaThongL921
9:28 p.m. 13 Tháng 10, 2021
-
0
longkold00
9:39 p.m. 13 Tháng 10, 2021
-
1
VoBaThongL921
9:43 p.m. 13 Tháng 10, 2021
-
1
VoBaThongL921
9:26 p.m. 13 Tháng 10, 2021
←
đã chỉnh sửa
→
-
1
longkold00
9:39 p.m. 13 Tháng 10, 2021
-
0
longkold00
9:34 p.m. 13 Tháng 10, 2021
8 bình luận nữaa làm như em thì bị tle nốt cái cuối :>
Anh để ý thấy vòng lặp for bên trong của sàng sẽ bắt đầu chạy từ i * 2, vậy chỉ cần cho vòng lặp ngoài duyệt đến limit / 2 là được ạ
và em không cho giá trị của chính nó vào tổng các ước của số đó. Ví dụ số 8 thì em chỉ tính là 7 thôi ạ (vì 1 + 2 + 4 = 7)
mơm em nhó :V
anh cẩn thận số 1 nhé, vì số ước của nó chỉ là 1 thôi ạ
UwU vậy mà vẫn tle:) anh thử xài vector đi: vector<int> a(lim + 9, 1)
cuối cùng sau 7749 lần thử a đã ac :>
a nàm hết òi + để thư viện iostream nhưng lúc thì test 13 tạch lúc thì test 14 :> cay qué em ới 🙂