Tóm tắt đề bài

Nhập một số nguyên dương \(k\). Một số nguyên dương \(x\) được gọi là ước nguyên tố của \(k\) nếu \(x \mid k\) và \(x\) là số nguyên tố. Hãy tính và in ra tổng các ước nguyên tố (phân biệt) của \(k\).

Ví dụ: \(k=21=3\cdot 7\) nên tổng là \(3+7=10\).

Phân tích

• Ta cần cộng các thừa số nguyên tố khác nhau của \(k\) (không tính lũy thừa nhiều lần).
  • Ví dụ \(k=12=2^2\cdot 3\) thì đáp án là \(2+3=5\).
• Ràng buộc tới \(k \le 10^{16}\): không thể sàng tới \(10^8\) hay lớn hơn.
• Nhận xét quan trọng:
  • Nếu ta thử chia \(k\) bởi các số \(i\) từ \(2\) tới \(\sqrt{k}\), mỗi khi tìm thấy \(i\) là ước thì \(i\) là một thừa số nguyên tố (sau khi xử lý đúng), và ta có thể loại bỏ toàn bộ bội số của \(i\) khỏi \(k\).
  • Sau khi chia hết các ước nhỏ, nếu phần còn lại \(k>1\) thì phần đó chắc chắn là một số nguyên tố (vì nếu hợp số thì phải có ước \(\le \sqrt{k}\)).

Hướng giải quyết

Nhận xét

• Để đảm bảo chỉ cộng mỗi ước nguyên tố một lần, khi gặp \(i\) chia hết \(k\):
  1. Cộng \(i\) vào đáp án.
  2. Chia \(k\) cho \(i\) liên tục cho tới khi không còn chia hết nữa (loại bỏ lũy thừa của \(i\)).
• Vòng lặp chỉ cần chạy khi \(i^2 \le k\) (vì nếu \(k\) còn hợp số thì phải có ước không vượt quá căn bậc hai).

Thuật toán (đúng như code AC)

1. Đọc \(n\) (chính là \(k\)), đặt sum = 0.
2. Với \(i = 2\) tăng dần, trong khi \(i^2 \le n\):
   • Nếu \(n \bmod i = 0\):
     • sum += i
     • Trong khi \(n \bmod i = 0\): n /= i
   • Tăng \(i\) lên \(1\).
3. Sau vòng lặp, nếu \(n > 1\) thì sum += n (vì \(n\) lúc này là một ước nguyên tố còn lại).
4. In sum.

Minh họa nhanh với \(k=21\)

• \(i=2\): không chia.
• \(i=3\): chia, cộng \(3\), chia hết \(3\) được \(n=7\).
• Dừng vì \(i^2=16 > 7\).
• \(n=7>1\) nên cộng thêm \(7\). Tổng \(=10\).

Lưu ý / Pitfall

• Phải dùng kiểu long long vì \(k\) có thể tới \(10^{16}\).
• Điều kiện vòng lặp nên là i*i <= n với i kiểu long long để tránh tràn (với \(10^{16}\) thì \(i \le 10^8\), vẫn an toàn trong long long).

Độ phức tạp

• Thời gian: \(O(\sqrt{k})\) trong trường hợp xấu nhất (khi \(k\) là số nguyên tố lớn).
• Bộ nhớ: \(O(1)\).

Code tham khảo

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

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n;
    cin >> n;

    ll sum = 0;

    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;                 // i là một ước nguyên tố (cộng 1 lần)
            while (n % i == 0) n /= i; // loại bỏ toàn bộ lũy thừa của i
        }
    }

    if (n > 1) sum += n; // phần còn lại (nếu có) là một số nguyên tố

    cout << sum;
    return 0;
}