CSES - Counting Divisor | Đếm ước

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Pypy 3 1.5s
Python 3 3.5s
Tác giả:
Flower_On_Stone , Phuc_QrdA5
Dạng bài
Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho \(n\) số nguyên. Với mỗi số, hãy cho biết số lượng ước của nó.

Ví dụ, nếu \(x = 18\), câu trả lời đúng là \(6\) vì các ước của nó là \(1,2,3,6,9,18.\)

Input

  • Dòng đầu tiên chứa một số nguyên \(n\)
  • Sau đó là \(n\) dòng, mỗi dòng chứa một số nguyên \(x\)

Output

  • Đối với mỗi số nguyên, in ra số lượng ước của nó.

Constraints

  • \(1 \leq n \leq 10^5\)
  • \(1 \leq x \leq 10^6\)

Example

Sample input

3
16
17
18

Sample output

5
2
6

Bình luận


  • 0
    tantaidepzai    1:12 p.m. 11 Tháng 9, 2024

    dế mà 1500 chẳng khác j cho


    • 0
      vietnammuonnam_mvn    5:30 p.m. 24 Tháng 8, 2024

      import sys
      import math

      MAX = 10**6
      divisors = [0] * (MAX + 1)

      for i in range(1, MAX + 1):
      for j in range(i, MAX + 1, i):
      divisors[j] += 1

      input = sys.stdin.read
      data = input().split()
      n = int(data[0])
      results = []

      for i in range(1, n + 1):
      x = int(data[i])
      results.append(str(divisors[x]))

      sys.stdout.write("\n".join(results) + "\n")
      Giải thích:
      Giải thích đoạn mã:
      Khởi tạo mảng divisors:

      divisors[j] lưu trữ số lượng ước của số j.
      divisors có kích thước từ 0 đến 10^6.
      Tính toán số lượng ước:

      Vòng lặp đầu tiên: Với mỗi số i từ 1 đến MAX, bạn sẽ đi qua các bội số của i và tăng giá trị của divisors[j] (nơi j là các bội số của i).
      Đọc dữ liệu đầu vào:

      input = sys.stdin.read sẽ đọc tất cả các dòng đầu vào cùng một lúc, sau đó chia nhỏ thành danh sách các chuỗi qua split().
      Xử lý các yêu cầu:

      Duyệt qua từng số trong danh sách và tìm số lượng ước của nó từ mảng divisors, sau đó lưu trữ vào results.
      In kết quả:

      Kết quả được nối lại thành một chuỗi lớn và in ra một lần duy nhất, giúp tiết kiệm thời gian in

      1 phản hồi

      • 0
        TH06_2024    8:29 a.m. 23 Tháng 8, 2024

        ezz gg 1500
        công thức có trg sách hết


        • 0
          BestFlo2k9    2:50 p.m. 27 Tháng 6, 2024

          include <bits/stdc++.h>

          define ll long long

          using namespace std;
          ll demuoc(ll n){
          ll h = sqrt(n),dem = 0;
          for (ll i = 1;i <= h;i++){
          if (n % i == 0){
          dem+=2;
          }
          }
          if (h*h == n){
          dem--;
          }
          return dem;
          }
          ll n,a[100005];
          int main(){
          cin >> n;
          for (ll i = 1;i <= n;i++){
          cin >> a[i];
          }
          for (ll i = 1;i <= n;i++){
          cout << demuoc(a[i]) << "\n";
          }
          return 0;
          }


          • 0
            PhucDepZai    9:14 p.m. 8 Tháng 6, 2024

            bài này chắc nhiều solution nhất LQDOJ rồi=)))


            • -1
              danghoang    12:19 a.m. 9 Tháng 2, 2024

              Đếm ước như bt duyệt từ 1-> sqrt(n) cs AC:))

              #include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n, i, x, d, q;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> q;
    while(q--)
    {
        cin >> n;
        d = 0;
        for(int i = 1; i*i <= n; i++)
        {
            if(n % i == 0)
            {
                if(n/i == i) d++;
                else d += 2;
            }
        }
        cout << d << '\n';
    }
}


              • -2
                vietanhvmo    9:19 a.m. 18 Tháng 11, 2023

                https://ideone.com/v7U6Ok


                • -2
                  QuangTue    5:12 p.m. 13 Tháng 11, 2023

                  Hint

                  include <iostream>

                  include <vector>

                  include <cmath>

                  using namespace std;

                  int countDivisors(int x) {
                  if (x <= 0) return 0;
                  int result = 1;

                  for (int i = 2; i <= sqrt(x); i++) {
    if (x % i == 0) {
        int k = 0;
        while (x % i == 0) {
            k++;
            x /= i;
        }
        result *= (k + 1);
    }
}

if (x > 1) result *= 2;
return result;

                  }

                  int main() {
                  ios::sync_with_stdio(0);
                  cin.tie(0);cout.tie(0);
                  int n;
                  cin >> n;

                  while (n--) {
    int x;
    cin >> x;
    cout << countDivisors(x) << "\n";
}

return 0;

                  }


                  • 1
                    penistone    3:40 a.m. 24 Tháng 10, 2023
                    Hint

                    Cách không tối ưu là duyệt 🙂 nhưng phân tích thừa số nguyên tố kết hợp với sàng nguyên tố thì sẽ AC bài này (dù hơi lâu)
                    Có thể tham khảo tại đây: https://ideone.com/eteDZu


                    • 0
                      N7hoatt    9:10 a.m. 30 Tháng 8, 2023 ← đã chỉnh sửa

                      Với \(n\) số nguyên cho trước, hãy cho biêt số lượng ước của từng số.

                      Input

                      • Dòng đầu tiên gồm số nguyên \(n\): số lượng số nguyên.
                      • \(n\) dòng tiếp theo, mỗi dòng gồm một số nguyên \(x\).

                      Output

                      • In số ước của mỗi số.

                      Constraints

                      • \(1 \leq n \leq 10^5\).
                      • \(1 \leq x \leq 10^6\).

                      Example

                      Test

                      Input 
                      3
16
17
18
                      Output 
                      5
2
6
                      Note
                        • 2 bình luận nữa