PRE THI HUYỆN #04

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Lát cắt hình chữ nhật 100 (p) 1.0s 256M
2 Lũy thừa 100 (p) 1.0s 256M
3 Biến đổi 100 (p) 1.0s 256M
4 Tổng chữ số nguyên tố 100 (p) 1.0s 256M

1. Lát cắt hình chữ nhật

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: latcathcn.inp Output: latcathcn.out

Cho \(1\) tờ giấy hình chữ nhật có kích thước \(n\)x\(m\). Cần cắt tờ giấy thành các ô vuông \(1\)x\(1\).
Mỗi lát cắt được phép cắt dọc (hết chiều dọc) hoặc cắt ngang (hết chiều ngang) theo cạnh của một mảnh giấy

Yêu cầu

  • Đếm số lần cắt ít nhất để cắt tờ giấy thành các ô vuông \(1\)x\(1\)

Dữ liệu vào

  • Ghi \(2\) số nguyên dương \(n\) ,\(m\) là chiều dài và chiều rộng của tờ giấy hình chữ nhật.(\(n, m \leq\) \(10^9\))

Dữ liệu ra

  • In ra \(1\) số là số lần cắt để cắt tờ giấy thành các ô vuông \(1\)x\(1\)
Ví dụ:
LATCATHCN.INP 
3 1
LATCATHCN.OUT 
2

2. Lũy thừa

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: apowb.inp Output: apowb.out

Cho \(2\) số nguyên \(a\),\(b\).

Yêu cầu

  • Hãy tính kết quả của phép tính \(a^b\) mod (\(10^9\) + 7).

Dữ liệu

  • Ghi \(2\) số nguyên dương \(a\),\(b\) (\(a, b \leq 10^9\)).

Kết quả

  • In ra \(1\) số duy nhất là kết quả của phép tính trên

Ràng buộc

  • Subtask \(1\): \(50\%\) số test với \(a,b\) \(\leq\) \(10^6\)
  • Subtask \(2\): \(50\%\) số test với \(a,b\) \(\leq\) \(10^9\)
Ví dụ
APOWB.INP 
3 5
APOWB.OUT 
243

3. Biến đổi

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: biendoi.inp Output: biendoi.out

Cho 1 dãy n số nguyên \({a_1, a_2, a_3, ... a_n}\) và dãy B rỗng. Trên dãy B, bạn hãy thực hiện n phép biến đổi. Với phép biến đổi thứ i:

  • Thêm \({a_i}\) vào cuối dãy B.
  • Đảo ngược thứ tự các phần tử của dãy B.

Yêu cầu

  • Bạn hãy tìm kết quả của dãy B sau khi thực hiện n phép biến đổi.

Dữ liệu

  • Dòng đầu tiên, chứa số nguyên dương \(n(1 \leq N \leq 2.10^5)\).
  • Dòng tiếp theo, chứa \(n\) số nguyên \(32\) bit \({a_1, a_2, a_3,..., a_n}\).

Kết quả

  • In ra dãy B sau khi thực hiện n phép biến đổi
Ví dụ:
BIENDOI.INP 
4
1 2 3 4
BIENDOI.OUT 
4 2 1 3

4. Tổng chữ số nguyên tố

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: tcsnt.inp Output: tcsnt.out

Cho \(t\) yêu cầu, với mỗi yêu cầu gồm \(2\) số nguyên \(l\), \(r\). Được biết số nguyên tố là số chỉ có \(2\) ước số là \(1\) và chính nó.

Yêu cầu

  • Đếm số lượng số có tổng các chữ số là số nguyên tố từ \(l\) tới \(r\).

Dữ liệu

  • Dòng đầu tiên, chứa số nguyên dương \(t\) là số lượng yêu cầu.
  • \(t\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên dương \(l\), \(r\).

Kết quả

  • In ra \(t\) dòng, mỗi dòng in ra \(1\) số nguyên là số lượng số có tổng các chữ số là tố nguyên tố từ \(l\) tới \(r\).

Ràng buộc

  • Subtask \(1\): \(25\%\) số test với \(t = 1\) và \(l, r \leq 2*10^6\)
  • Subtask \(2\): \(25\%\) số test với \(t \leq 100\) và \(l, r \leq 2*10^6\)
  • Subtask \(3\): \(50\%\) số test với \(t\) \(\leq\) \(100\) và \(l\), \(r\) \(\leq\) \(10^{18}\)
Ví dụ
TCSNT.INP 
3
2 10
4 7
1 100
TCSNT.OUT 
4
2
37