Tích các ước số của một số trong C++

Cho số n. Nhiệm vụ: tìm tất cả ước số của n và tính tích của chúng. Ước số là số chia hết n (kể cả 1 và n).

Ví dụ 1

Input – n = 18

Output – 5832

Giải thích: Ước: 1, 2, 3, 6, 9, 18. Tích = 1×2×3×6×9×18 = 5832.

Ví dụ 2

Input – n = 9

Output – 27

Giải thích: Ước: 1, 3, 9. Tích = 27.

Thuật toán (duyệt đến √n)

1. Duyệt i từ 1 đến √n.
2. Nếu n % i == 0:
   • Nếu i == n/i (ước chính phương): nhân tích với i một lần.
   • Ngược lại: nhân tích với i và n/i.
3. Trả về tích (mod 1e9 nếu cần tránh tràn).

Ví dụ code

#include <iostream>
#include <cmath>
using namespace std;

const long long MOD = 1000000000; // 1e9

long long productOfFactors(int n) {
    long long product = 1;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            if (i == n / i) {
                product = (product * i) % MOD;
            } else {
                product = (product * i) % MOD;
                product = (product * (n / i)) % MOD;
            }
        }
    }
    return product;
}

int main() {
    int n = 9;
    cout << productOfFactors(n) << endl;
    return 0;
}

Kết quả

27

Công thức toán học: Nếu n có k ước số, tích tất cả ước số = n^(k/2). Vì các ước số đi thành cặp (d, n/d) tích bằng n. Nếu n là số chính phương, ước giữa √n tự cặp với chính nó.

Ví dụ: n=18 có 6 ước → tích = 18^(6/2) = 18³ = 5832. n=9 có 3 ước → tích = 9^(3/2) = 9×√9 = 27.