Đề TS 10 LQĐ Đà Nẵng - Bài 1: số anh em

#1

Mọi người có ai có cách giải hoàn chỉnh cho bài ko ạ, em chỉ làm được đến subtask 1 thôi.

Một số được coi là số anh em nếu tổng các chữ số và tổng bình phương các chữ số (trong hệ thập phân) của nó là số nguyên tố. Ví dụ: số 23, số 41 là các số anh em.

Yêu cầu : Hãy xác định số lượng số anh em trong đoạn [L,R].

Input : Đọc từ file văn bản ANHEM.INP gồm hai số nguyên L và R (1<L,R≤10^18).
Output : Ghi ra file văn bản ANHEM.OUT một số nguyên là kết quả cần tìm.

Scoring

  • Subtask 1:40% test có 1<L,R≤10^6.
  • Subtask 2:30% test có 1<L,R≤10^9.
  • Subtask 3:30% test có 1<L,R≤10^18
#2

Mình không nhìn thấy đề, có phải link bị lỗi không bạn?

1 Like
#3

Mình có sửa lại đề rồi ấy

#4

Trước hết bạn bám vào dữ kiện

Giả sử ta biểu diễn n dưới dạng n = \overline{a_{k-1}...a_{0}}.

Định nghĩa tổng các chữ số của n là s(n) = a_{k-1} + ... + a_{0}, tổng bình phương các chữ số của n là s2(n) = a_{k-1}^2 + ... + a_{0}^2.

Với n < 10^{18} thì s(n) \le 9*18 = 162 và s2(n) \le 9^2 * 18 = 1458.

Mặt khác, s2(n) \le [s(n)]^2 = a_{k-1}^2 + ... + a_{0}^2 + 2 \sum_{i \ne j} a_i a_j \le 9^2 (k+1) \le 1539.

Do vậy, ta tìm các s(n) nguyên tố thoả mãn [s(n)]^2 \le 1539 \Rightarrow s(n) \le 39.

Suy ra s(n) \in \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}.

Với các s(n) nhỏ như vậy, bạn viết ra các tập chữ số khác 0 có tổng bằng s(n), tính tổng bình phương tập các chữ số đó xem có thoả mãn là số nguyên tố không, rồi đếm (có thể thêm vài chữ số 0 rồi shuffle các chữ số). Bước này ta sử dụng kỹ thuật backtracking.

Ví dụ, 7 = 2 + 2 + 3 có 2^2 + 2^2 + 3^3 = 17 thoả mãn là số nguyên tố. Do vậy, các số 223, 232, 322, 2023, 2032, 20230000… đều là số anh em.

2 Likes
#5

Em vẫn chưa hiểu lắm dòng s2(n)<=[s(n)]^2 trở đi ạ

#6

[s(n)]^2 = a_{k-1}^2 + ... + a_{0}^2 + 2 \sum_{i \ne j} a_i a_j đơn thuần là phá ngoặc ra.

\begin{matrix} [s(n)]^2 &= (a_{k-1} + ... + a_{0})^2\\ &= a_{k-1}^2 + ... + a_{0}^2 + 2(a_0 a_1 + ... a_0 a_{k-1} + a_1 a_2 + ... + a_1 a_{k-1} + ...)\\ \end{matrix}

a_0 a_1 + ... a_0 a_{k-1} + a_1 a_2 + ... + a_1 a_{k-1} + ... có thể viết gọn lại thành \sum_{i < j} a_i a_j (tổng các tích của cặp 2 chữ số bất kì khác vị trí, có tổng cộng \frac{k(k-1)}{2} cặp tất cả).

Do 0 \ge a_i \ge 9 nên

  • a_i a_j \ge 0\ \forall i, j \Rightarrow s2(n) \le [s(n)]^2.

  • a_i^2,\ a_i a_j \le 9 * 9\ \forall i, j \Rightarrow [s(n)]^2.

Suy ra s2(n) \le [s(n)]^2 = a_{k-1}^2 + ... + a_{0}^2 + 2 \sum_{i < j} a_i a_j \le 9^2 k + 2 \frac{k(k-1)}{2} 9^2 = 9^2 k^2.

Giờ mới thấy mình cộng sai :crazy_face:

#8

vậy em nghĩ code cũ ko ổn lắm ạ

#9

Code cũ của bạn như thế nào, mình không thấy ở đây :crazy_face:

#10

sr =)) nãy mk nhầm ấy

#11

Bạn thử cài đặt bằng backtracking xem nào.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?