Đếm số ước - LCOJ: Luyện Code Online Judge

UOCSO - Đếm số ước

Điểm: 1,00 (OI)

Giới hạn thời gian: 0.5s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho ~N~ số nguyên dương ~a_1,a_2,…,a_N~. Với mỗi giá trị ~a_i, ∀i=1..N~, hãy cho biết ~a_i~ có bao nhiêu ước số?

Input

Dòng đầu chứa một số nguyên dương ~N~;
Dòng thứ hai chứa ~N~ số nguyên dương ~a_1,a_2,…,a_N~.

Giới hạn:

~60\%~ số điểm ứng với các test có ~N≤1000,1≤a_i≤10^3, ∀i=1..N~;
~40\%~ số điểm ứng với các test có ~N≤1000,1≤a_i≤10^8, ∀i=1..N~.

Output

Ghi trên ~N~ dòng, dòng thứ ~i~ ghi số ước số của ~a_i~.

Sample

Input #1

6
2 3 5 7 4 8

Output #1

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

taidotai đã bình luận lúc 12, Tháng 6, 2026, 13:27 ← chỉnh sửa →

include <bits/stdc++.h>

using namespace std ;

bool ngto(int n ) { if (n < 2 ) return false ; if (n == 2) return true ; if (n % 2 == 0) return false ;

for (int i = 2 ; i < n ; i++ ){
    if (n % i == 0 ) {
        return false ;
    }
}
return true ;

}

int main () { int n ; cin >> n ;

for (int i = 0 ; i < n ; i++ ){
    int x ;
    cin >> x ;

    int d = 0 ;

    if (ngto(x)) {
        cout << "2" << endl ;
    }

    else {
        for (int i = 1 ; i <= x ; i++ ){
            if (x % i == 0 ) {
                d++ ;
            }
        }
        cout << d << endl ;
    }
}
return 0 ;

} một ý tưởng khác để làm bài này những sẽ bị tle

spoil! ý tưởng

duyệt đến căn bậc 2 của a[i] để đếm ước

code tham khảo (C++)

    #include <bits/stdc++.h>

    using namespace std;

    long long demuoc(long long x) {
        long long dem = 0, n = sqrt(x);
        for (int i = 1; i <= n; ++i)
            if (x % i == 0) dem += 2;
        if (n * n == x) dem--;
        return dem;
    }

    int main() {
        ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

        int n;
        cin >> n; 

        for (int i = 1; i <= n; ++i) {
            int x; 
            cin >> x; 
            cout << demuoc(x) << endl; 
        }
    }