Đếm số dhprime
Xem PDF
Điểm:
200 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Rùa có một chuỗi ký tự \(S\) chỉ bao gồm các ký tự chữ số và ký tự ?. Cậu sẽ thay thế mỗi ký tự ? trong chuỗi đó bằng một trong những ký tự chữ số 0-9, sao cho tạo thành một chuỗi mới là một số nguyên hợp lệ (không bắt đầu bằng số 0) và cậu muốn biết là cậu có thể tạo ra bao nhiêu số nguyên tố bằng cách đó.
Input
- Chuỗi \(S\), chỉ bao gồm các ký tự chữ số và ký tự
?. Độ dài chuỗi \(S\) không quá \(7\).
Output
- In ra một số nguyên, là số lượng số nguyên tố mà Rùa có thể tạo thành bằng cách đã mô tả.
Example
Test 1
Input
1?Output
4Note
Cậu có thể thế ? bằng một trong ba ký tự 1, 3, 7, 9.
Test 2
Input
?Output
4
Bình luận
Sàn số nguyên tố số nào có thể trở thành từ chuỗi s tức là phải không quá lớn nhất tạo ra từ chuỗ s và không bé hơn số nhỏ nhất phải tạo ra từ chuỗi s . Chạy mất 0,39ms
Edit:mình có sử dụng hàm pow nếu bạn code có hàm pow giống mình có thể tự viết một hàm pow khác nó sẽ cải thiệt đáng kể thời gian 0,28
đệ quy lmj cho mệt
Ý tưởng dùng sàng đánh dấu các số nguyên tố từ
1->10^7trong mảng, sau đó dùng đệ quy tính ra tất cả các số có thể được tạo ra từ xâu sau đó kiểm tra bằng mảng đã đánh dấu \(O(1)\).độ phức tạp: sàng \(O(nloglogn)\)+tạo ra các số \(O(9^k)\) với \(k\) là số kí tự
'?'trong mảng:)
dấu "?" có bắt buột là những số giống nhau ko ??