Tác giả:

• Hà Phước Vũ - Lớp 10A5, trường THPT Chuyên Lê Quý Đôn, Đà Nẵng.

Bài 1: Số mũ lớn nhất.

Tags: math - 900.

1. Đề bài.

Cho số nguyên dương

$n$, hãy tìm số tự nhiên

$k$ lớn nhất thỏa mãn

$2^k$ là ước của

$n!$.

2. Lời giải.

Với bài này, ta chỉ việc tìm số mũ đúng của

$2$ trong

$n!$ bằng công thức Legendre, cụ thể là:

• $\lfloor \frac{n}{2}\rfloor +\lfloor \frac{n}{4}\rfloor +\lfloor \frac{n}{8}\rfloor +...++\lfloor \frac{n}{2^i}\rfloor$ với
  $i$ là số tự nhiên lớn nhất thỏa mãn
  $2^i\le n$.

Bạn có thể xem chứng minh của công thức trên tại đây.

Độ phức tạp của ý tưởng trên là

$O(lo{g}_2(n))$, dưới đây là code cài đặt tham khảo.

void solve() {
    long long n, ans = 0; cin >> n; 
    while (n > 0) {
        ans += n/2;
        n /= 2;
    }
    cout << ans << endl;
}

Bài 2: Số nhỏ nhất.

Tags: greedy - 1100.

1. Đề bài.

Cho một xâu

$s$ gồm các chữ cái Latin thường với tối thiểu

$n$ chữ số thập phân. Hãy tìm xâu con có độ dài

$n$ của

$s$ thỏa mãn các kí tự của nó là các chữ số và tạo thành số nhỏ nhất trong hệ thập phân.

2. Lời giải.

Ta đặt

$len$ là độ dài của xâu

$s$ sau khi loại bỏ các chữ cái xuất hiện trong nó.

Dễ dàng thấy các chữ cái Latin xuất hiện trong

$s$ là không cần thiết, vì vậy ta có thể loại bỏ nó khỏi xâu.

Để tìm ra xâu con kết quả, ta sẽ ưu tiên lấy các chữ số đứng trước nhỏ nhất có thể. Từ vị trí của chữ số đó, ta sẽ tìm các kí tự tiếp theo với ý tưởng tương tự. Nếu trong đoạn ưu tiên có các chữ số nhỏ nhất trùng nhau, ta sẽ ưu tiên lấy chữ số có vị trí nhỏ nhất để các lần lấy sau được tối ưu.

Từ ý tưởng trên, ta có thể tham lam như sau:

• Chạy
  $i$ từ
  $n$ về
  $1$ tương ứng với
  $n$ lần lấy.
• Lấy chữ số trong đoạn ưu tiên
  $[pos,len-i+1]$ theo ý tưởng trên.
• Gọi
  $p$ là vị trí của chữ số được lấy, khi đó ta sẽ đặt
  $pos=p$ và tiếp tục thực hiện thao tác trên cho đến khi
  $i=1$.

Độ phức tạp của ý tưởng trên là

$O(n)$, dưới đây là code cài đặt tham khảo.

void solve() {
    int n, pos = 0; string s; 
    cin >> n >> s; s = delete(s); // Xóa các chữ cái.
    for (int i = n; i >= 1; i--) {
        int cur = 57, p;
        for (int j = pos; j <= s.size()-i; j++) {
            if (s[j] < cur) {
                cur = s[j], p = j+1;
            }
        }
        cout << cur-48; pos = p;
    }
    cout << "\n"; 
}  

Bài 3: Tọa độ nguyên dương.

Tags: math - 1300.

1. Đề bài.

Cho

$1$ đoạn thẳng được nối bởi

$2$ điểm

$(a,b)$ và

$(c,d)$ trên mặt phẳng

$Oxy$, hãy tìm số lượng điểm có tọa độ nguyên nằm trên đoạn thẳng đó (không tính

$2$ đầu đoạn thẳng).

2. Lời giải.

Giả sử

$2$ điểm được cho là

$A(a,b)$ và

$B(c,d)$ và một điểm

$C(x,y)$ (khác

$A$ và

$B$) nằm trên đoạn thẳng

$AB$. Ta gọi

$2$ điểm

$E$ là điểm nằm trên đường tròn đường kính

$AB$,

$D$ là hình chiếu của

$C$ trên

$AE$. Để đơn giản, ta có thể dựng

$x_E=a,y_E=d$.

Để

$C$ có tọa độ nguyên thì

$AD$ và

$CD$ phải có độ dài là số nguyên không âm. Điều này chỉ xảy ra khi và chỉ khi

Từ nhận xét trên, kết quả cần tìm của ta là

$gcd(|a-c|,|b-d|)-1$.

Độ phức tạp của ý tưởng trên là

$O(lo{g}_{2}n)$, dưới đây là code cài đặt tham khảo.

void solve() {
    long long a, b, c, d; cin >> a >> b >> c >> d;
    cout << __gcd(abs(a-c), abs(b-d))-1 << "\n";
}