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

Sample output

5
2
6

Bình luận

C++

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define v vector
#define p pair
using namespace std;
char el = '\n';
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);

void solve() {
    int x;
    cin >> x; v<int> alphas;
    for (int i = 2; i*i*i <= x; i++) {
        if (x % i == 0) {
            int alpha = 0;
            while (x % i == 0) {
                x /= i;
                alpha++;
            }
            alphas.push_back(alpha);
        }
    }
    if (x != 1) {
        alphas.push_back(1);
    }

    // for (int i : alphas) cout << i << " ";
    int z = 1;
    for (int i : alphas) {
        z *= (i + 1);
    }
    cout << z << el;
}

int main() {
    fast;

    int n;
    cin >> n;
    while (n--) {
        solve();
    }
}

// Định lý cơ bản của số học

O(cbrt n log n)

-2

Phản hồi

danh3003 • 4:38 p.m. 9 Tháng 1, 2025 •
Lưu ý cho những ai làm bài này chưa AC:

Khi duyệt qua các số từ \(1\) -> \(\sqrt{x}\), ta nên dùng:

C++
for (int i = 1; i * i < x; i++){ //Thuật toán tính số ước mà không kiểm tra x là số chính phương }if ((int) sqrt(x) == sqrt(x)){ //Cộng thêm 1 vào bước đếm }

Thay vì:

C++
for (int i = 1; i <= pow(x, 0.5); i++){ //Thuật toán tính số ước mà cần kiểm tra x là số chính phương }

Nguyên do:

Nếu mỗi lần lặp đều cần kiểm tra x là số chính phương thì độ phức tạp sẽ cộng thêm \(\sqrt{x}\) \(\Rightarrow\) kiểm tra x là số chính phương ở cuối. Nếu \(x = a^2\) thì biến đếm \(+1\).

Hàm \(sqrt()\) được tạo ra để chuyên dùng tính \(\sqrt{x}\) nên sẽ có khả năng tính toán nhanh hơn hàm \(pow(x, 0.5)\).
2
Phản hồi Chia sẻ

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

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

-1
Phản hồi Chia sẻ

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

0
Phản hồi Chia sẻ

1 phản hồi

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
Phản hồi Chia sẻ

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
Phản hồi Chia sẻ

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

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

0
Phản hồi Chia sẻ

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

Phản hồi

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

https://ideone.com/v7U6Ok

-2
Phản hồi Chia sẻ

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;

}

-4

Phản hồi

4 bình luận nữa

CSES - Counting Divisor | Đếm ước

Input

Output

Constraints

Example

Bình luận

include <bits/stdc++.h>

define ll long long

Hint

include <iostream>

include <vector>

include <cmath>