HSG9 Cà Mau 2026 - Ma trận ước số

Xem dạng PDF

Gửi bài giải

Điểm: 5,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    thinhphamminh274  đã bình luận lúc 10, Tháng 11, 2026, 5:19 ← chỉnh sửa

    GIẢI THUẬT: MA TRẬN ƯỚC SỐ

    1. Hàm tính số lượng ước số d(x)

    • Mục tiêu: Đếm tổng số lượng ước số dương của một số nguyên $x$.
    • Cách thực hiện:
      • Khởi tạo biến đếm res = 0.
      • Duyệt biến $i$ từ $1$ đến $\sqrt{x}$ (tương ứng với điều kiện vòng lặp i * i <= x).
      • Với mỗi giá trị $i$, kiểm tra xem $i$ có phải là ước của $x$ hay không (x % i == 0):
        • Nếu $i \times i \neq x$: Tăng biến res lên 2 (res += 2) vì ứng với ước $i$ sẽ có thêm ước đối xứng là $x / i$.
        • Nếu $i \times i == x$: Tăng biến res lên 1 (res++) do đây là trường hợp chính phương ($i$ chính là căn bậc hai của $x$).
      • Trả về kết quả res.

    2. Chương trình chính (main)

    • Bước 1 (Đọc dữ liệu): Nhập hai số nguyên $n$ (kích thước bảng $n \times n$) và $k$ (số lượng ước tối đa).
    • Bước 2 (Khởi tạo): Khởi tạo biến cur = 1 để lưu giá trị các số điền vào ma trận, bắt đầu từ $1$.
    • Bước 3 (Duyệt ma trận): Sử dụng hai vòng lặp for lồng nhau để duyệt qua từng ô của ma trận vuông kích thước $n \times n$:
      • Vòng lặp ngoài quản lý các hàng $i$ (từ $1$ đến $n$).
      • Vòng lặp trong quản lý các cột $j$ (từ $1$ đến $n$).
    • Bước 4 (Xử lý và in kết quả tại mỗi ô):
      • Gọi hàm d(cur) để tính số lượng ước của số hiện tại cur.
      • So sánh kết quả với $k$:
        • Nếu d(cur) <= k: In ra ký tự * (đại diện cho ô tô đậm).
        • Ngược lại: In ra ký tự ..
      • Tăng biến cur lên 1 đơn vị sau mỗi ô (cur++).
    • Bước 5 (Xuống dòng): Sau khi hoàn thành một hàng (kết thúc vòng lặp của cột $j$), thực hiện xuống dòng để chuyển sang hàng tiếp theo của ma trận.
      #include <bits/stdc++.h>
      #define ll long long
      #define Sonic() cin.tie(NULL)->syncwithstdio(0);
      #define el '\n'
      using namespace std;
      ll d(ll x){
          ll res=0;
          for(ll i=1;ii<=x;i++){
              if(x%i==0&&ii!=x)res+=2;
              else if(i*i==x)res++;
          }
          return res;
      }
      
      
      

      int main(){ Sonic(); ll n,k;cin>>n>>k; ll cur=1; for(ll i=1;i<=n;i++){ for(ll j=1;j<=n;j++){ if(d(cur)<=k)cout<<'*'; else cout<<'.'; cur++; } cout<<el; } return 0; }