Câu 1 (5,0 điểm) SỐ HỌC

Khám phá về các con số, An thấy nhiều điều thú vị. Chẳng hạn như: Số chính phương hay còn gọi là số hình vuông là số tự nhiên có căn bậc hai là một số tự nhiên, số ước dương của một số chính phương là một số lẻ, số nguyên tố là số chỉ có đúng 2 ước là 1 và chính nó, … Tiếp tục với những khám phá đó, An đi tìm con số tự nhiên đó đúng 3 ước dương và nhận thấy những mối liên hệ thú vị khác. Ví dụ 25 có 3 ước dương là 1, 5, 25 Cho số tự nhiên n, hãy tìm số tự nhiên m nhỏ nhất thỏa mãn: m > n và m có đúng 3 ước dương.

Dữ liệu vào:

Từ file văn bản số SOHOC.INP gồm số tự nhiên n.

Dữ liệu ra:

Từ file văn bản SOHOC.OUT gồm một số tự nhiên m tìm đượcc

Ví dụ:

Giới hạn:

• 40% số điểm tương ứng với ~0 < n \le 10^3~
• 60% số điểm tương ứng với ~10^3 < n \le 10^6~
• 80% số điểm tương ứng với ~10^6 < n \le 10^{12}~

Câu 2: (4,0 điểm) TỔNG SỐ MŨ CHẴN – LẺ

(Cho số tự nhiên N (~N\geq2~), ta có thể phân tích N thành tích các thừa số nguyên tố với dạng ~N=P_1^{x_1}\times P_2^{x_2}\times\ldots\times P_k^{x_k}~, trong đó ~P_1<P_2< \ldots < P_k~ là các số nguyên tố và ~x_1,x_2, \ldots ,x_k>0~ . Gọi ~S~ là tổng các số mũ ~x_i~ có giá trị chẵn và ~P~ là tổng các số mũ ~x_j~ có giá trị lẻ

Chú ý là ~S+P = x_1+x_2+\ldots+x_k~

Yêu cầu:

hãy đưa ra giá trị của ~S~ và ~P~

Dữ liệu vào:

Cho trong file văn bản SumExpo.Inp gồm các số tự nhiên N (~2\le N~)

Dữ liệu ra:

Ghi ra file văn bản SumExpo.out gồm 2 dòng:

• Dòng thứ nhất ghi ra giá trị ~S~
• Dòng thứ hai ghi ra giá trị của ~P~

Ví dụ :

Giới hạn:

• Có 30% số test ứng với ~N < 10^6, P_1<P_2<\ldots<P_k<20~ trong đó ~N=P_1^{x_1}\times P_2^{x_2}\times\ldots\times P_k^{x_k}~</li>
• Có 30% số test ứng với ~N < 10^6~
• Có 40% số test ứng với ~N < 10^{12}~

Câu 3: (4,0 điểm) MẬT KHẨU

Việc bảo vệ máy tính để hạn chế người khác thâm nhập là một vấn đề đặt ra cho mọi nguời sử dụng máy tính. Để tăng tính an toàn trong lưu trữ, Bạn Nam đã quyết định giấu mật khẩu truy cập máy tính của mình vào một xâu ~S~ với một qui ước sao cho khi cần Nam có thể lấy lại được mật khẩu từ ~S~. Là một người yêu thích số học Nam chọn mật khẩu P là một số tự nhiên và mã hóa ~P~ = ~P_1~ × ~P_2~ × ~\ldots~ × ~P_n~, với ~P_i~ là số nguyên dương và đem dấu các số ~P_i~ vào một xâu ký tự ~S~. Chẳng hạn xâu ~S~ = "~mat22b3ma6c7d8~" chứa mật khẩu là ~22176~ vì ~P = 22~ × ~3 ~×~ 6~ × ~7~ × ~8~.

Yêu cầu:

Cho một xâu ký tự ~S~, tìm mật khẩu ~P~ đã giấu trong xâu ~S~. Vì kết quả có thể rất lớn, in ra số dư của mật khẩu P khi chia cho ~10^9+7~.

Dữ liệu vào:

Tệp MATKHAU.INP gồm 1 dòng duy nhất chứa xâu ~S~ chỉ gồm các chữ cái in thường và các chữ số.

Dữ liệu ra:

Tệp MATKHAU.OUT gồm 1 dòng chứa số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Câu 4: (4,0 điểm) ĐẾM HÌNH VUÔNG

An có N đoạn thẳng. An thấy rằng một số đoạn thẳng có cùng chiều dài, do đó cậu ta có thể xếp thành những hình vuông từ những đoạn thẳng bằng nhau đó.

Cậu ta muốn biết hình vuông lớn nhất mà cậu ta có thể tạo ra bằng cách sử dụng những đoạn thẳng đó như thế nào. Vì số lượng các đoạn thẳng lớn cậu ta không thể làm điều đó bằng tay. Bạn có thế giúp cậu ấy biết diện tích tối đa của hình vuông lớn nhất có thể được tạo thành. Đồng thời, cũng tính toán xem có bao nhiêu hình vuông như vậy có thể được tạo thành từ các đoạn thẳng.

Dữ liệu vào:

Dòng đầu tiên chứa một số nguyên T biểu thị số bộ dữ liệu kiểm tra. Mỗi bộ dữ liệu gồm:

• Dòng đầu chứa một số nguyên N biểu thị số đoạn thẳng
• Dòng tiếp theo chứa N số nguyên được phân cách bằng dấu cách biểu thị độ dài của mỗi đoạn thẳng

Dữ liệu ra:

Ứng với mỗi bộ dữ liệu vào, in ra một dòng chứa hai số nguyên cách nhau bởi dấu cách biểu thị diện tích tối đa của hình vuông có thể tạo thành và số lượng hình vuông có diện tích tối đa như vậy. Nếu không có hình vuông nào được hình thành thì in ra số -1.

Ví dụ:

Giới hạn:

• ~1 \le T \le 100; 1 \le N le 250~
• ~1 \le~ độ dài mỗi đoạn thẳng ~\le 10^3~

Câu 5: (3,0 điểm) TỔNG TIỀN TỐ

Cho dãy số nguyên gồm n phần tử ~a_1, a_2, a_3,\ldots , a_n~ (~|a_i| \le 10^9~). Cho giá trị ~x~ và ~q~ câu hỏi có dạng ~A(u,v)~ với ~S(u,v)~ là tổng các giá trị của các phần tử từ ~u~ đến ~v~.

Yêu cầu:

Đếm xem trong ~q~ câu hỏi có bao nhiêu câu hỏi có giá trị nhỏ hơn ~x~.

Dữ liệu vào:

• Dòng đầu tiên chứa ba số nguyên dương ~n, x, q~ (~x \le 10^9, q \le 10^5~)
• Dòng thức hai chứa ~a_1, a_2, a_3,\ldots , a_n~ (~|a_i| \le 10^9~).
• ~q~ dòng tiếp theo mỗi dòng chứa hai số nguyên dương ~u, v (1 \le u \le v \le n)~

Dữ liệu ra:

• In ra một số nguyên là số lượng câu hỏi có giá trị nhỏ hơn ~x~

  Ví dụ:

Giới hạn:

• 50% số điểm tương ứng với: ~0 \le n \le 500~
• 30% số điểm tương ứng với ~500 < n \le 10^4~
• 20% số điểm tương ứng với ~10^4 < n \le 10^5~