Dãy số nhân tính - LCOJ: Luyện Code Online Judge

NHANTINH - Dãy số nhân tính

Điểm: 1,00 (OI)

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

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 một dãy gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~, hãy viết chương trình kiểm tra xem dãy có phải là dãy nhân tính hoàn toàn hay không.

Một dãy số ~a_1, a_2, ..., a_n~ là một dãy nhân tính hoàn toàn nếu ~a_{ij} = a_i × a_j~ với mọi số nguyên ~i, j~ sao cho ~1 ≤ i, j ≤ n~ và ~1 ≤ i×j ≤ n~.

Input

Dòng đầu tiên gồm một số nguyên ~n~ là độ dài của dãy số nguyên cần kiểm tra;
Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(0 ≤ a_i ≤ 10^9)~ mô tả dãy số cần kiểm tra.

Giới hạn:

Subtask #1: ~1 ≤ n ≤ 10^3~.
Subtask #2: ~1 ≤ n ≤ 10^5~.

Chú ý: Nếu bài làm của bạn chỉ ghi ra YES hoặc chỉ ghi ra NO sẽ được ~0~ điểm.

Output

Nếu dãy số được cho là dãy nhân tính hoàn toàn, in ra YES, ngược lại, in ra NO.

Sample

Input #1

10
1 2 3 4 5 6 7 8 9 10

Output #1

YES

Input #2

10
1 1 2 2 4 2 6 4 6 4

Output #2

NO

Problem source: Kc97ble - Free Contest

Bình luận

Please read the guidelines before commenting.

kietjumper đã bình luận lúc 4, Tháng 1, 2026, 4:35 ← chỉnh sửa →

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector< long long> a(n + 1); 

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; i * j <= n; ++j) {
            if (a[i * j] != a[i] * a[j]) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }

    cout << "YES" << endl;
    return 0;
}

Chỉ in ra YES -> AC 9 test; Chỉ in ra NO -> AC 41 test

-1

hoamz đã bình luận lúc 12, Tháng 10, 2024, 5:15

test 6 la sao vay mn