Ước số và tổng ước số

Xem PDF
Tác giả:
corona
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Cho số nguyên dương \(N (N \leq 2∗10^9)\).

Yêu cầu: Đếm số lượng ước số của \(N\) và tổng các ước số của \(N\).

Input

  • Số nguyên dương \(N\)

Output

  • Chứa hai số nguyên là sô lượng ước số và tổng các ước của \(N\)

Example

Test 1

Input 
10
Output 
4 18
Note
  • Số \(10\) có ước là \(1\) \(2\) \(5\) \(10\) và tổng \(1 + 2 + 5 + 10 =18\)

Bình luận


  • -1
    TIT_manh    8:38 p.m. 29 Tháng 4, 2024
    Mình xin chia sẻ cách giải bài này như sau:
    • Duyệt i từ 1 đến căn bặc 2 của n sao cho khi gặp ước của n thì:
      • Tăng biến đếm ước.
      • Tăng tổng ước lên i đơn vị.
      • Nếu thấy rằng i khác n/i thì:
        ++ Tăng biến đếm ước.
        ++ Tăng tổng ước lên n/i đơn vị.
    Code mẫu C++

    include <bits/stdc++.h>

    using namespace std;
    int main() {
    long long n, dem, s;
    cin >> n;
    dem = 0;
    s = 0;
    for (int i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
    dem++;
    s = s + i;
    if (i != n / i) {
    dem++;
    s = s + (n / i);
    }
    }
    }
    cout << dem << " " << s;
    return 0;
    }

      • 5 bình luận nữa