SUMDIV - Tính tổng các ước số

Xem dạng PDF
Gửi bài giải
Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Tác giả:
Hiếu Nguyễn
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Tính tổng của tất cả các ước nguyên dương của số nguyên dương ~n~.

Input

  • Dòng đầu ghi số nguyên dương ~T~ là số bộ test.
  • ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~.

Giới hạn:

  • ~1 ≤ T ≤ 10^3, 1 ≤ n ≤ 10^6~.

Output

  • Với mỗi số nguyên dương ~n~, ghi ra trên một dòng số nguyên dương là tổng của tất cả các ước của ~n~.

Sample

Input #1
3
3
8
15
Output #1
4
15
24

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.


  • 0
    hungthinhtongquang  đã bình luận lúc 9, Tháng 6, 2026, 13:22

    hi


  • 0
    mducc  đã bình luận lúc 23, Tháng 4, 2026, 14:46

    spoil! 

    ý tưởng: 
dùng sàng ước để tối ưu tốc độ xử lý từng test

    code tham khảo (c++) 

        #include <bits/stdc++.h>

    using namespace std;

    const int lim = 1e6;
    int uoc[lim+1];

    void sang(int n = lim) {
        for(int i = 1; i <= n; ++i)
            for(int j = i; j <= n; j += i) uoc[j]+=i;
    }
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

        sang();

        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            cout << uoc[n] << '\n';
        }

    }

  • 0
    lamnguyen7316  đã bình luận lúc 26, Tháng 1, 2026, 9:29

    Code full AC:

    inputstr = input() t = int(inputstr)

    for _ in range(t): n = int(input()) tong = 0 i = 1 while i * i <= n: if n % i == 0: tong += i
    if i * i != n:
    tong += n // i i += 1 print(tong)


  • 1
    nguyenanhchuong  đã bình luận lúc 5, Tháng 11, 2025, 11:40

    khá


  • 0
    anle  đã bình luận lúc 17, Tháng 10, 2025, 5:52

    sao test 3 lai bi qua thoi gian vay a, ai chi giup em vs a


    • 0
      dangbachpho1101  đã bình luận lúc 9, Tháng 1, 2026, 13:30

      chạy tới n/2 là được rồi.


  • -2
    super_god  đã bình luận lúc 8, Tháng 10, 2024, 2:51

    hello ae


  • 1
    kietjumper  đã bình luận lúc 26, Tháng 9, 2024, 12:56 ← sửa 2

    Thuật toán

    Duyệt ~i~ từ ~1~ -> ~n~/~i~, nếu ~n~ chia hết cho ~i~, sum += ~i~ + ~n~/~i~, sau đó kiểm tra xem ~i~ * ~i~ có bằng n hay không, nếu bằng, sum -= ~i~. Cuối cùng in ra sum là xong!