Editorial for uoc1: Tính tổng ước 1

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 d sao cho d là ước của A nhưng d KHÔNG phải là ước của B. Nói cách khác, ta cần tìm tập hợp ước chung của A và B, loại chúng khỏi tập ước của A, rồi tính tổng các phần còn lại. Tên bài toán 'Tính tổng ước 1' và các ví dụ cho thấy ta chỉ xét các ước của A, không cần xét các số khác.

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

Cách Duyệt qua các ước của A (Optimized)

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

int main() {
    long long a, b;
    scanf("%lld %lld", &a, &b);

    long long sum = 0;
    long long limit = sqrt(a);

    // Duyệt từ 1 đến căn bậc hai của A để tìm các ước
    for (long long i = 1; i <= limit; i++) {
        if (a % i == 0) {
            long long j = a / i;

            // Kiểm tra ước i
            if (b % i != 0) {
                sum += i;
            }

            // Kiểm tra ước j (nếu khác i)
            if (i != j && b % j != 0) {
                sum += j;
            }
        }
    }

    printf("%lld\n", sum);
    return 0;
}

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

Đây là phương pháp tối ưu nhất được chọn từ các submissions. Thay vì duyệt từ 1 đến A, ta chỉ cần duyệt từ 1 đến căn bậc hai của A (sqrt(A)). Nếu i là ước của A thì j = A/i cũng là ước của A. Với mỗi cặp ước (i, j) tìm được, ta kiểm tra xem chúng có phải là ước của B hay không (bằng cách lấy số dư B chia cho i hoặc j). Nếu không phải là ước của B, ta cộng giá trị đó vào tổng. Ta phải chú ý trường hợp A là số chính phương (i == j) để tránh cộng trùng.

Cách Brute Force (Duyệt toàn bộ)

#include <stdio.h>

int main() {
    long long a, b;
    scanf("%lld %lld", &a, &b);

    long long sum = 0;
    // Duyệt tất cả các số từ 1 đến A
    for (long long i = 1; i <= a; i++) {
        // Nếu i là ước của A và không là ước của B
        if (a % i == 0 && b % i != 0) {
            sum += i;
        }
    }

    printf("%lld\n", sum);
    return 0;
}

• Time Complexity: O(A)
• Space Complexity: O(1)

Đây là cách tiếp cận đơn giản nhất nhưng không đủ nhanh cho các test case lớn (A lên tới 10^9). Phương pháp này lặp qua tất cả các số từ 1 đến A, kiểm tra xem số đó có phải là ước của A hay không, và nếu có thì kiểm tra xem nó có phải là ước của B không. Nếu A = 10^9, vòng lặp sẽ chạy 10^9 lần, dẫn đến TLE (Time Limit Exceeded).

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

Bài học kinh nghiệm

• Bài toán yêu cầu tổng các ước của A trừ đi các ước chung của A và B (ước của A mà cũng là ước của B).
• Có thể tối ưu hóa bằng cách chỉ duyệt lên đến căn bậc hai của A để tìm ước, giảm độ phức tạp từ O(A) xuống O(sqrt(A)).
• Cần phân biệt rõ điều kiện: chỉ cộng d vào tổng nếu d là ước của A và d KHÔNG chia hết cho B.

Lỗi thường gặp

• Dùng biến kiểu int cho A, B khi A có thể lên tới 10^9, dẫn đến tràn số. Cần dùng long long.
• Quên kiểm tra điều kiện i != j khi A là số chính phương, dẫn đến cộng một ước bị nhân đôi.
• Lầm tưởng rằng cần tính tổng các ước của A rồi trừ đi tổng các ước của B. Sai hoàn toàn vì các ước của B không nằm trong tập ước của A thì không ảnh hưởng, và các ước chung không đơn giản là tổng ước của B.