Editorial for uoc2: Tính tổng ước 2

Hiểu bài toán

Cho hai số nguyên dương A và B. Yêu cầu tính tổng tất cả các số nguyên dương là ước chung của cả A và B. Ví dụ: với A=15, B=25, các ước chung là 1 và 5, tổng là 6.

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

Cách Brute Force - Duyệt qua các số từ 1 đến min(A, B)

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

int main() {
    long long a, b;
    scanf("%lld %lld", &a, &b);
    long long min = (a < b) ? a : b;
    long long sum = 0;
    for (long long i = 1; i <= min; i++) {
        if (a % i == 0 && b % i == 0) {
            sum += i;
        }
    }
    printf("%lld", sum);
    return 0;
}

• Time Complexity: O(min(A, B)) - Trong trường hợp xấu nhất có thể lên tới ~10^9
• Space Complexity: O(1)

Phương pháp này duyệt qua tất cả các số từ 1 đến số nhỏ hơn của A và B, kiểm tra xem số đó có phải là ước chung không, nếu có thì cộng vào tổng. Đơn giản nhưng quá chậm cho dữ liệu lớn.

Cách Optimized - Duyệt ước của số nhỏ hơn

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

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    int min = (a < b) ? a : b;
    int max = (a > b) ? a : b;
    int count = 0;
    for (int i = 1; i * i <= min; i++) {
        if (min % i == 0) {
            int j = min / i;
            if (max % i == 0) count += i;
            if (max % j == 0 && i != j) count += j;
        }
    }
    printf("%d", count);
    return 0;
}

• Time Complexity: O(sqrt(min(A, B)))
• Space Complexity: O(1)

Thay vì duyệt đến min(A,B), ta chỉ cần duyệt đến căn bậc hai của min(A,B). Nếu i là ước của min thì j = min/i cũng là ước. Kiểm tra xem i và j có chia hết cho max không. Nếu i khác j thì cộng cả hai vào. Ví dụ: min=25, duyệt i=1..5, được các cặp (1,25), (5,5).

Cách Optimal - Dùng GCD và duyệt ước của GCD

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

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    long long a, b;
    scanf("%lld %lld", &a, &b);
    long long g = gcd(a, b);
    long long sum = 0;
    for (long long i = 1; i * i <= g; i++) {
        if (g % i == 0) {
            sum += i;
            if (i != g / i) sum += g / i;
        }
    }
    printf("%lld", sum);
    return 0;
}

• Time Complexity: O(sqrt(gcd(A, B)))
• Space Complexity: O(1)

Ước chung của A và B chính là các ước của GCD(A,B). Ta tính GCD của A và B bằng thuật toán Euclid, sau đó tính tổng tất cả các ước của GCD bằng cách duyệt đến căn bậc hai của GCD. Đây là cách hiệu quả nhất.

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

Bài học kinh nghiệm

• Ước chung của A và B chính là các ước của GCD(A, B)
• Duyệt đến căn bậc hai của số cần kiểm tra giúp giảm độ phức tạp từ O(n) xuống O(sqrt(n))

Lỗi thường gặp

• Quên kiểm tra trường hợp i*i == g để không cộng ước trùng lặp
• Sử dụng biến int cho A, B lớn hơn 10^9 gây tràn số