https://chuyentinpbc.ucode.vn/contests/chu-de-so-hoc-1-68779

Bài 1.

Số chính phương là số tự nhiên bằng bình phương đúng của một số tự nhiên

Ví dụ: 

 là số chính phương vì 

. 

Yêu cầu: Cho 2 số nguyên dương 

: đếm xem có bao nhiêu số chính phương trong đoạn từ 

 đến

Dữ liệu: Vào từ file văn bản CAU1.INP gồm một dòng duy nhất ghi 2 số nguyên dương 

cách nhau 1 dấu cách.

Kết quả: Ghi ra file văn bản CAU1.OUT một số nguyên là số lượng các số chính phương trong đoạn

Ví dụ:

Sample InputSample Output
100 2005
5 253

Giới hạn:

Subtask 1: Có 30% số test tương ứng với 30% số điểm có  

Subtask 2: Có 70% số test tương ứng với 70% số điểm không có ràng buộc gì thêm.

Bài 2. Đếm ước

 Cho số nguyên dương 𝑁. Hãy đếm số lượng các ước dương của 𝑁. 

Dữ liệu cho trong tệp văn bản DemUoc.Inp gồm một số nguyên dương 𝑁.

 Kết quả ghi ra tệp văn bản DemUoc.Out là số lượng các ước dương của 𝑁.

 Ví dụ: 

DemUoc.InpDemUoc.OutGiải thích
646 có các ước dương: 1, 2, 3, 6. 
⇒ Số lượng các ước dương là 4.

Giới hạn:

 · Sub1: Có 75% số test ứng với 75% số điểm thỏa mãn 1 ≤ 𝑁 ≤ 106 ;

 · Sub 2: Có 25% số test ứng với 25% số điểm thỏa mãn 106 < N ≤ 1012 .

Bài 3

               Cho dãy A có n số nguyên dương  a1, a2,…,an và số nguyên k (1< k< 106) .

Yêu cầu: Tìm độ dài đoạn con ngắn nhất chứa đủ k phần tử mà số lượng ước của mỗi phần tử này là nhiều nhất trong dãy.

Dữ liệu: Vào từ tệp văn bản BAI3.INP

  • Dòng một là hai số nguyên dương n,k ;
  • Dòng hai là dãy A chứa n số nguyên dương a1, a2,…,an với 1< ai< 107 .

Các số nguyên trong tệp dữ liệu được ghi cách nhau ít nhất một dấu cách trống.

Kết quả: Ghi ra tệp văn bản BAI3.OUT một số nguyên thoả mãn yêu cầu, trường hợp không có đoạn con nào đủ k phần tử thoả mãn yêu cầu thì ghi -1.

Ví dụ:

BAI3.INPBAI3.OUTGiải thích
8 3
6 2 3 8 4 10 9 10
5- Các phần tử có cùng số lượng ước nhiều nhất là 6, 8, 10 và 10 (cùng có 4 ước);
- Đoạn con ngắn nhất chứa đủ 3 phần tử có cùng số lượng ước nhiều nhất là đoạn [4, 8] độ dài là 5 gồm các phần tử thoả mãn là: 8, 10 và 10.   

Ràng buộc:

  • 50% số test tương ứng với 50% số điểm có n< 103, k< 103, ai< 106;
  •   30% số test tương ứng với 30% số điểm có n < 105, k< 104, ai< 106;
  • 10% số test tương ứng với 10% số điểm có n< 106, k< 106, ai< 106;
  • 10% số test tương ứng với 10% số điểm không có ràng buộc gì.