思路

题意简述：在 $1\sim n$ 中选出 $m$ 个互不相同的整数，使它们两两互质（$\gcd(a_i,a_j)=1$），输出任意一组；不存在则输出 -1。注意 $1$ 与任何正整数都互质，因此 $1$ 也可以选用。

要让两两互质，最自然的方式是让每个数使用互不相同的质因子。质数天然满足这一点：任意两个不同的质数互质，而且数值尽可能小，最容易落在 $[1,n]$ 内。因此用「$1$ 加上若干个质数」来构造。

设不超过 $n$ 的质数有 $cnt$ 个，从小到大为 $p_1=2,p_2=3,\dots,p_{cnt}$。

构造方案：

• 若 $m\le cnt$：直接输出前 $m$ 个质数 $p_1,\dots,p_m$，它们两两互质且都不超过 $n$。
• 若 $m=cnt+1$：输出 $1,p_1,p_2,\dots,p_{cnt}$，共 $cnt+1=m$ 个数。$1$ 与任何数互质，其余都是互不相同的质数，合法。
• 若 $m>cnt+1$：输出 -1。

为什么 $m>cnt+1$ 时一定无解： 设选出的 $m$ 个数中有 $k$ 个数大于 $1$，它们按从小到大排列为 $x_1<\dots<x_k$。两两互质且都大于 $1$，意味着它们的最小质因子互不相同（否则两个数有公共质因子，$\gcd>1$）。这 $k$ 个互不相同的质数中第 $i$ 小的至少是 $p_i$，而 $x_i$ 不小于自己的最小质因子，所以 $x_i\ge p_i$，特别地 $x_k\ge p_k$，于是 $p_k\le x_k\le n$，即 $k\le cnt$。又因为数字互不相同，最多只有一个数是 $1$，所以 $m=k+[有 1]\le cnt+1$。因此 $m>cnt+1$ 时不存在合法构造。

实现步骤：

1. 先用埃氏筛预处理出 $10^6$ 以内的所有质数（从 $2$ 开始），存进 primes。
2. 每组询问用 upper_bound 求出不超过 $n$ 的质数个数 $cnt$。
3. 按上面的三种情况输出：前 $m$ 个质数、$1$ 加全部质数、或 -1。

复杂度：筛法 $O(N\log\log N)$，其中 $N=10^6$；每组数据求 $cnt$ 是 $O(\log N)$，输出 $O(m)$。空间 $O(N)$ 存筛表和质数表。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << '\n'
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
#define pdd pair<dd,dd>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;

const int N = 1e6+10;
// p[i] 为筛标记：1 表示 i 是质数
int p[N];
// 从小到大保存 [2, N-1] 内的所有质数；1 不是质数，单独处理
vector<int> primes;
int n,m;

// 埃氏筛，预处理出 n 以内的质数（默认筛到 N-1）
void sieve(int n = N-1) {
    if (n >= N) n = N-1;
    for (int i = 0; i <= n; ++i) p[i] = 1;
    if (n >= 0) p[0] = 0;
    if (n >= 1) p[1] = 0;

    for (int i = 2; i * i <= n; ++i) {
        if (p[i]) {
            // 从 i*i 开始把 i 的倍数标记为合数
            for (long long j = 1LL * i * i; j <= n; j += i) p[j] = 0;
        }
    }

    primes.clear();
    for (int i = 2; i <= n; ++i) if (p[i]) primes.pb(i);
}

void go(){
    cin>>n>>m;

    // 统计不超过 n 的质数个数
    int cnt = upper_bound(primes.begin(), primes.end(), n) - primes.begin();

    if(m <= cnt){
        // 质数够用：直接输出前 m 个质数
        for(int i=0;i<m;i++){
            cout<<primes[i]<<' ';
        }
    }else if(m == cnt+1){
        // 质数有 cnt 个，还差一个，用 1 补上（1 与任何数互质）
        cout<<1;
        for(int i=0;i<cnt;i++){
            cout<<' '<<primes[i];
        }
    }else{
        // 即使把 1 也算上也不够 m 个，无解
        cout<<-1;
    }
    el;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    // 只筛一次，供所有测试用例共用
    sieve();
    cin >>_;
    while(_--){
        go();
    }
    return 0;
}