Kỳ thi kiểm tra tháng 9

Hãy tìm tất cả các số nguyên tố trong đoạn [\(A;B\)]

Input

• Gồm 2 số nguyên \(A;\ B\) cách nhau bởi 1 dấu cách (\(1\leq A\leq B\leq 10^7\))

Output

• Ghi ra tất cả các số nguyên tố trong khoảng [\(A;B\)]. Mỗi số trên 1 dòng.

Example

1 10

2
3
5
7

Hôm nay coder bin9638 top 1 thế giới nhận lời thách đấu của coder thứ 7 tỉ thế giới algorit solo giải 1 bài toán do giáo sư nhphucqt đưa ra.

Bài toán là cho 2 số tự nhiên \(l,r\). Hãy đếm số lượng số nguyên tố giữa chúng.

bin9638 loay hoay mãi mà vẫn chưa nghĩ ra cách làm trong khi algorit đã sắp xong, các bạn hãy giúp bin9638 chiến thắng trong cuộc solo này nhé. Nếu giải được thì bin9638 sẽ chia 1 nửa phần thưởng của cuộc solo này cho các bạn đó !

- Yêu cầu: đếm số lượng số nguyên tố trong đoạn \([l,r]\)

Input

• Dòng đầu tiên chứa số nguyên dương \(q\) là số đoạn \([l,r]\)
• \(q\) dòng tiếp theo mỗi dòng chứa \(2\) số nguyên dương \(l\) và \(r\)

Output

• Gồm \(q\) dòng, dòng thứ \(i\) ghi một số là số các số nguyên tố trong đoạn \([l,r]\) thứ \(i\) đã cho.

Constraints

• \(1 \leq l,r \leq 2 \times 10^8\)
• \(1 \leq q \leq 10^5\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(q \leq 10^3\), \(l\) và \(r \leq 10^7\)
• Subtask \(2\) (\(50\%\) số điểm): \(q \leq 10^5\), \(l\) và \(r \leq 2 \times 10^8\)

Example

1
2 5 

3

Rôn mua một bộ đèn trang trí gồm \(n\) đèn (\(1 \le n \le 1000\)). Mỗi đèn có một công tắc để bật hay tắt riêng đèn đó. Mỗi giây Rôn có thể bật hoặc tắt một bóng đèn tùy chọn. Ban đầu tất cả các bóng đều ở trạng thái tắt. Một cấu hình của bộ đèn là trạng thái khi một số đèn nào đó được bật sáng, những đèn còn lại tắt. Rôn đặc biệt thích một số cấu hình vì chúng có vẻ phù hợp với khung cảnh căn phòng của Rôn.

Mỗi trạng thái của bộ đèn được biểu diễn bằng một xâu \(n\) ký tự từ tập \(\{0, 1\}\). Ký tự thứ \(i\) xác định trạng thái đèn thứ \(i\), \(0\) tương ứng với trạng thái đèn tắt, \(1\) tương ứng với trạng thái đèn được bật sáng. Ví dụ, với \(n = 3\) và Rôn đặc biệt thích \(3\) cấu hình \(\{1, 0, 1\}, \{0, 1, 0\}, \{1, 1, 1\}\). Để kiểm tra xem cấu hình nào là thích hợp nhất Rôn phải lần lượt bật tắt một số đèn. Trong trường hợp này Rôn cần \(4\) giây để xem xét hết mọi cấu hình.

Yêu cầu

Cho biết \(n\) và \(m\), trong đó \(m\) là số cấu hình khác nhau mà Rôn đặc biệt yêu thích (\(1 \le m \le 15\)). Hãy xác định thời gian tối thiểu cần thiết để kiểm tra hết tất cả các trạng thái mà Rôn quan tâm.

Input

• Dòng đầu tiên chứa \(2\) số nguyên \(n\) và \(m\).
• Mỗi dòng trong \(m\) dòng tiếp theo chứa xâu \(n\) ký tự xác định một cấu hình Rôn yêu thích.

Output

• Một số nguyên duy nhất là thời gian tối thiểu để kiểm tra hết các cấu hình.

Example

3 3
101
010
111

4

Constraints

• \(1 \le n \le 1000\).
• \(1 \le m \le 15\).

In ra tất cả cặp số nguyên tố \(A,B(A\le B)\) thỏa mãn \(A+B\) cũng là số nguyên tố và \(A+B\le N\). (In theo thứ tự từ điển từ bé đến lớn)

Input

• Dòng thứ nhất chứa số nguyên dương \(N(1\le N\le 10^6)\)

Output

• Dòng thứ nhất in ra số \(k\) - số lượng cặp \((A,B)\) thỏa mãn yêu cầu bài toán

• In ra \(k\) cặp \((A,B)\) thỏa mãn yêu cầu bài toán (theo thứ tự từ điển từ bé đến lớn).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(0<N\le 10\)

• Subtask \(2\) (\(20\%\) số điểm): \(0<N\le 10^4\)

• Subtask \(3\) (\(60\%\) số điểm): \(\text{Còn lại}\)

Example

7

2
2 3
2 5

Nam là nhà khảo cổ học, anh đã thăm dò và phát hiện nhiều cổ vật rất có giá trị. Để dễ quản lí các cổ vật, anh ta đánh số thứ tự cho các cổ vật, có \(n\) cổ vật được đánh số \(1, 2, 3, ... n\). Nam muốn biết với n cổ vật thì tổng các chữ số dùng để đánh số thứ tự là bao nhiêu?

Ví dụ: Có \(n=12\) cổ vật thì tổng các chữ số để đánh số thứ tự là : \(1+2+3+4+5+6+7+8+9+1+0+1+1+1+2=51\)

Yêu cầu Cho giá trị \(n\), hãy tính tổng các chữ số dùng cho việc đánh số thứ tự \(n\) cổ vật

Dữ liệu: Một số tự nhiên \(n\ (n≤10^{12})\).

Kết quả: Một số tự nhiên duy nhất là tổng các chữ số dùng để đánh số thứ tự của \(n\) cổ vật.

Scoring

• Có 60% số điểm của bài toán với \(n≤1 000 000\).
• Có 40% số điểm của bài toán với \(1 0000 000≤n≤10^{12}\).

Example

12

51

8

36