Editorial for uocle: Tìm ước số lẻ lớn nhất của số N

Hiểu bài toán

Cho một số nguyên dương N, yêu cầu tìm ước số lẻ lớn nhất của N nhưng phải nhỏ hơn N. Ví dụ, với N = 15, các ước là 1, 3, 5, 15. Ước số lẻ lớn nhất nhỏ hơn 15 là 5. Nếu N là số lẻ, ước số lẻ lớn nhất của N là chính N, do đó ước lẻ lớn nhất nhỏ hơn N sẽ là N chia cho ước số lẻ nhỏ nhất của N (hoặc ước nguyên tố nhỏ nhất). Nếu N là số chẵn, ta có thể loại bỏ hết các thừa số 2 (chia N cho 2 cho đến khi kết quả là số lẻ), lúc đó số thu được chính là ước lẻ lớn nhất của N (vì N = 2^k * M, ước lẻ lớn nhất là M, và M < N).

Các cách tiếp cận

Cách Brute Force (Tìm ước và kiểm tra)

#include <stdio.h>
#include <math.h>

int a[1000001];
void solve(int n)
{
    int cnt=0;
    for(int i=1; i<=sqrt(n); i++)
    {
        if(n%i==0)
        {
            a[cnt] = i;
            cnt++;
            a[cnt] = n/i;
            cnt++;
        }
    }
    int key = a[0];
    for(int i=0; i<cnt; i++)
    {
        if(a[i]>key && a[i]%2!=0 && a[i]<n) key = a[i];
    }
    printf("%d\n", key);
}
int main()
{
    int t; scanf("%d", &t);
    while(t--)
    {
        int n; 
        scanf("%d", &n);
        solve(n);
    }
    return 0;
}

• Time Complexity: O(sqrt(N))
• Space Complexity: O(sqrt(N))

Phương pháp này tìm tất cả các ước số của N bằng cách lặp từ 1 đến căn bậc hai của N. Sau đó, nó lọc ra các ước số lẻ và chọn ra ước số lẻ lớn nhất nhỏ hơn N. Cách này dễ hiểu nhưng chậm và tốn bộ nhớ lưu trữ các ước số so với các phương pháp tối ưu khác.

Cách Brute Force (Tối ưu)

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
int main() {
    int t;
    scanf("%d",&t);
    for (int i = 0;i < t;i++){
        int n;
        scanf("%d",&n);
        int tmp = n;
        while (tmp%2==0){
            tmp/=2;
        }
        if (tmp == n){
            int ans = 1;
            for (int j = 3;j*j <= n;j+=2){
                if (n % j ==0){
                    ans = n / j;
                    break;
                }
            }
            printf("%d\n",ans);
        } else {
            printf("%d\n",tmp);
        }
    }
    return 0;
}

• Time Complexity: O(sqrt(N))
• Space Complexity: O(1)

Cách tiếp cận này chia vấn đề làm 2 trường hợp:

1. Nếu N chẵn: Lặpwhile để chia N cho 2 cho đến khi kết quả là số lẻ. Số thu được chính là đáp án.
2. Nếu N lẻ: Tìm ước số lẻ nhỏ nhất của N bằng cách lặp các số lẻ từ 3 đến sqrt(N). Ước lẻ lớn nhất nhỏ hơn N sẽ là N chia cho ước lẻ nhỏ nhất này. Nếu không tìm thấy ước nào (N là số nguyên tố), đáp án là 1. Phương pháp này không cần lưu mảng ước số, tối ưu hơn về bộ nhớ và thường nhanh hơn trong thực tế.

Cách Mathematical Optimization (Logic tối ưu)

#include <stdio.h>
#include <math.h>

void giai() {
    int n;
    scanf("%d", &n);

    // Trường hợp n là số chẵn
    if (n % 2 == 0) {
        while (n % 2 == 0) {
            n /= 2;
        }
        printf("%d\n", n);
    } 
    // Trường hợp n là số lẻ
    else { 
        int smallest_prime_factor = n;

        // Tìm ước nguyên tố nhỏ nhất của n
        for (long long i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                smallest_prime_factor = (int)i;
                break;
            }
        }
        printf("%d\n", n / smallest_prime_factor);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        giai();
    }
    return 0;
}

• Time Complexity: O(sqrt(N))
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu và hiệu quả nhất.

• Nếu N là số chẵn: N = 2^k * M (với M là số lẻ). Ước lẻ lớn nhất của N là M. Việc chia N cho 2 liên tục cho đến khi không chia hết 2 nữa sẽ thu được M.
• Nếu N là số lẻ: Gọi D là ước lẻ lớn nhất của N nhỏ hơn N. Vì N là số lẻ, D cũng là ước của N. Ta có N = D * k. Để D lớn nhất, k phải nhỏ nhất. k nhỏ nhất là ước số lẻ nhỏ nhất của N (trường hợp N nguyên tố thì k=1). Vậy D = N / (ước lẻ nhỏ nhất của N). Việc tìm ước lẻ nhỏ nhất chỉ cần lặp từ 3 đến sqrt(N). Độ phức tạp: O(sqrt(N)) cho mỗi test case.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Phân tích N thành thừa số nguyên tố: N = 2^k * P1^a1 * P2^a2 * ... (với Pi là số lẻ). Ước lẻ lớn nhất của N là tích các thừa số lẻ.
• Trường hợp N chẵn: Ước lẻ lớn nhất nhỏ hơn N là N sau khi loại bỏ hết các thừa số 2 (N / 2^k).
• Trường hợp N lẻ: Ước lẻ lớn nhất nhỏ hơn N là N chia cho ước lẻ nhỏ nhất của N.

Lỗi thường gặp

• Quên kiểm tra điều kiện ước số phải nhỏ hơn N (ví dụ: nếu N là số nguyên tố lẻ, ước lẻ lớn nhất nhỏ hơn N là 1, không phải N).
• Xử lý sai kiểu dữ liệu khi tính toán căn bậc hai (nên dùng biến long long cho vòng lặp để tránh tràn số khi i*i).
• Nếu N là số lẻ và là số nguyên tố, vòng lặp tìm ước sẽ không tìm được ước nào, cần gán đáp án mặc định là 1.