CSES - Counting Divisor | Đếm ước - LQDOJ: Le Quy Don Online Judge

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

13 bình luận nữa