Đếm ước số của n² không phải ước số của n trong C++

Giới thiệu

Bài toán: Cho số nguyên n, đếm số lượng ước số của n² mà KHÔNG phải là ước số của n.

Ví dụ với n = 6

• n = 6, n² = 36
• Ước của 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
• Ước của 6: 1, 2, 3, 6
• Ước của 36 KHÔNG phải ước của 6: 4, 9, 12, 18, 36 → 5 ước

Mã nguồn hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

int getNumberOfDivisors(int n) {
    int n_square = n * n;
    int divisors_count = 0;
    
    for (int i = 2; i <= n_square; i++) {
        if (n_square % i == 0 && n % i != 0) {
            divisors_count++;
        }
    }
    return divisors_count;
}

int main() {
    int n = 6;
    cout << getNumberOfDivisors(n) << endl;
    return 0;
}

Kết quả chạy chương trình

5

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

• Thời gian: O(n²) - duyệt từ 2 đến n²
• Không gian: O(1)

Tối ưu hóa bằng lý thuyết số

Có thể giải quyết nhanh hơn nhiều bằng cách sử dụng phân tích thừa số nguyên tố:

• Nếu n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ
• Số ước của n: (a₁+1)(a₂+1)...(aₖ+1)
• Số ước của n²: (2a₁+1)(2a₂+1)...(2aₖ+1)
• Kết quả = Số ước n² - Số ước n

Mã nguồn tối ưu (O(√n))

int countDivisors(int n) {
    int count = 1;
    for (int p = 2; p * p <= n; p++) {
        int exp = 0;
        while (n % p == 0) {
            n /= p;
            exp++;
        }
        count *= (exp + 1);
    }
    if (n > 1) count *= 2; // n còn lại là số nguyên tố
    return count;
}

int optimizedSolution(int n) {
    int original_n = n;
    int divisors_n = countDivisors(n);
    
    // Tính ước của n²
    n = original_n;
    int divisors_n2 = 1;
    for (int p = 2; p * p <= n; p++) {
        int exp = 0;
        while (n % p == 0) {
            n /= p;
            exp++;
        }
        divisors_n2 *= (2 * exp + 1);
    }
    if (n > 1) divisors_n2 *= 3; // 2*1+1 = 3
    
    return divisors_n2 - divisors_n;
}

Kết luận

Giải pháp đơn giản O(n²) dễ hiểu nhưng chậm với n lớn. Giải pháp tối ưu O(√n) sử dụng phân tích thừa số nguyên tố phù hợp cho n lớn (lên tới 10⁹ hoặc 10¹²).