C++ bài 9.A2 [Số nguyên tố & Sàng nguyên tố]: Những bó trúc

LÀM BÀI
Points: 10 (partial)
Time limit: 2.0s
Memory limit: 20M
Author:
hlk28chitinh
Problem type

5.3: Những bó trúc

Gấu Trúc FullHouse Dev rất thích ăn trúc và luôn mang trúc bên mình.

Anh ấy có N bó trúc, trong đó bó trúc thứ i chứa chính xác i thanh trúc nhỏ. Gấu Trúc FullHouse Dev muốn mang theo chính xác K bó trúc trong chuyến đi của mình.

Trong dịp này, anh ấy muốn chọn K bó trúc theo cách kỳ lạ: nếu cả bó trúc thứ i và j được chọn, thì i và j không được là số nguyên tố cùng nhau, với tất cả 1 ≤ i < j ≤ N.

Vui lòng giúp anh ấy chọn K bó trúc. Xuất một trong những lựa chọn có thể, sắp xếp theo thứ tự tăng dần.

INPUT FORMAT

Dòng đầu tiên của đầu vào chứa một số nguyên T, biểu thị số lượng test case. Dòng đầu tiên và duy nhất của mỗi test case chứa hai số nguyên cách nhau bởi một khoảng trắng N và K.

OUTPUT FORMAT

Đối với mỗi test case, xuất K số nguyên khác nhau, biểu thị số lượng bó trúc được chọn, trong đó các bó trúc được đánh số từ 1 đến N, sắp xếp theo thứ tự tăng dần. Nếu có nhiều giải pháp, bất kỳ giải pháp nào đều được chấp nhận. Nếu không thể chọn K bó trúc, in ra một số nguyên -1.

Ràng buộc
1 ≤ T ≤ 7
1 ≤ K ≤ N ≤ 777

Ví dụ 1:

Input:

2
100 3
100 100

Output:

35 45 63
-1

Giải thích:

Ví dụ trường hợp 1: Một trong những lựa chọn có thể là anh ấy chọn bó trúc thứ 35, bó trúc thứ 45 và bó trúc thứ 63. Bởi vì
GCD(35, 45) = 5,
GCD(35, 63) = 7,
GCD(45, 63) = 9.

Ví dụ trường hợp 2: Anh ấy phải chọn K = N = 100 bó trúc trong trường hợp này. Nhưng, ví dụ, cặp bó trúc thứ 3 và bó trúc thứ 5 không đáp ứng yêu cầu của anh ấy. Vì vậy, không thể chọn K bó trúc.

Comments


  • 0
    nhuhien1506  commented on June 10, 2026, 8:21 a.m.

    include <iostream>

    include <vector>

    using namespace std;

    void solve() { int N, K; if (!(cin >> N >> K)) return;

    if (K == 1) {
    cout << 1 << "\n";
    return;
}

if (K > N / 2) {
    cout << -1 << "\n";
    return;
}

for (int i = 1; i <= K; ++i) {
    cout << 2 * i << (i == K ? "" : " ");
}
cout << "\n";

    }

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

    int T;
if (cin >> T) {
    while (T--) {
        solve();
    }
}
return 0;

    }

Zalo