Đề TS 10 LQĐ Đà Nẵng 🐢

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 \le 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 \le 10^6\).
• Subtask \(2: 30\%\) test có \(1 <L, R \le 10^9\).
• Subtask \(3: 30\%\) test có \(1 <L, R \le 10^{18}\)

Example

10 11

1

50 100

8

Một xâu được gọi là đối xứng nếu xâu đó đọc từ trái sang phải cũng giống như đọc từ phải sang trái. Ví dụ: xâu \(\texttt{abba}\), \(\texttt{ata}\) là các xâu đối xứng.

Yêu cầu: Cho trước một xâu \(s\), xâu con của nó là một xâu có một hoặc nhiều kí tự liên tiếp nhau. Hãy xác định xem có bao nhiêu xâu con là xâu đối xứng trong xâu đã cho.

Input

Đọc từ file văn bản DOIXUNG.INP gồm duy nhất một dòng chứa xâu \(s\) chỉ chứa các chữ cái latinh thường, độ dài của xâu không quá 10 kí tự.

Output

Ghi ra file văn bản DOIXUNG.OUT một số duy nhất là số lượng xâu con xứng trong xâu đã cho.

Scoring

Xâu \(s\) chỉ bao gồm các chữ cái latinh in thường.

• Sub \(1: 30\%\) test có \(1 < |s| \le 500\)
• Sub \(2: 30\%\) test có \(500 < |s| \le 1000\).
• Sub \(3: 40\%\) test có \(1000 < |s| \le 10^5\)

Example

ata

4

aabbaa

11

Một đàn ong có \(N\) con được đánh số từ 1 đến \(N\), con thứ \(i\ (1 \le i\le N)\) có cân nặng là một số nguyên dương \(A_i\ (1 \le A_i \le 10^6)\). Biết rằng nếu một con ong có cân nặng \(X\) thì một ngày nó sản xuất được lượng mật ong là \(X \times f(X)\), với \(f(X)\) là số lượng ướ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

Đọc từ file văn bản MATONG.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương \(N\).
• Dòng thứ hai ghi lần lượt \(A_1, A_2,..., A_n\) cách nhau một dấu cách.

Output

Ghi ra file văn bản MATONG.OUT 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: 50\%\) test có \(1<N\le500\).
• Subtask \(2: 30\%\) test có \(500<N\le 1000\).
• Subtask \(3: 20\%\) test có \(1000< N \le 10^5\)

Example

4 
1 2 3 4

23

Anh Khoai được ông phú hộ hứa gả con gái với điều kiện làm việc không công cho ông ta mười năm và phải hoàn thành một nhiệm vụ ông ta giao cho. Sau mười năm làm việc anh Khoai tìm ông phú hộ để nhận nhiệm vụ cuối cùng. Vì không muốn gả con gái cho anh Khoai nên phú hộ yêu cầu anh mang về cho ông cây tre trăm đốt. Với sự giúp đỡ của ông bụt, anh Khoai đã mang về một trăm đốt tre cùng hai câu thần chú “khắc nhập” và “khắc xuất” để hoàn thành nhiệm vụ. Tuy nhiên, bằng cách nào đó ông phú hộ đã biết được sự việc và chuẩn bị sẵn rất nhiều đốt tre dài ngắn khác nhau và yêu cầu anh tạo thành cây tre có độ dài \(K\) từ những đốt tre đã có sẵn thì ông ta mới gả con gái cho.

Yêu cầu: Hãy giúp anh Khoai kiểm tra xem có bao nhiêu cách tạo ra cây tre có độ dài \(K\) từ những đốt tre đã có sẵn.

Input

Đọc từ file văn bản TRE.INP có cấu trúc như sau:

• Dòng đầu tiên chứa 2 số nguyên là \(N\) và \(K\ (1 \le N, K \le 10^5)\) trong đó \(N\) là số đốt tre, \(K\) là chiều dài cây tre cần tạo thành.
• Dòng 2 chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_n\) cách nhau một dấu cách lần lượt là chiều dài của \(N\) đốt tre \((A_i \le 10^5)\).

Output

Ghi ra file văn bản TRE.OUT một số duy nhất là số cách tạo thành cây tre có độ dài \(K\), chỉ cần in ra kết quả sau khi chia lấy dư cho \(10^9 + 7\).

Scoring

• Subtask \(1: 20\%\) test có \(N \le 10^2\).
• Subtask \(2: 40\%\) test có \(N \le 10^3\).
• Subtask \(3: 40\%\) giới hạn gốc.

Example

6 90
70 50 60 20 30 40

4