CSES - Counting Divisor | Đếm ước

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

Sample output

5
2
6

Bình luận

Đế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

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;

}

0

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

-1
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

7

chienthancontent 10:39 a.m. 17 Tháng 6, 2023

**Lưu ý: chỉ tham khảo khi quá bí
Solution: https://ideone.com/YfL2gM

-17

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.