题目传送门
分析：
题目要求需要让 \(\Omega(x)\) 最小，所以构造的每个数 \(x\) 必须得在质因子个数最少的情况下，和其他数要有至少 \(n - 1\) 个不同的 \(\gcd\)。
怎么才能得到这么多种 \(\gcd\)？让 \(x\) 的每个质因子都两两不同。只有这样构造才能在 \(x\) 的质因子中取任意多个，得到的积是两两不同的。不难发现组合方案一共有 \(2^{\Omega(x)}\) 种，那么输出的第一行至少为 \(\left\lceil\log_2n\right\rceil\)。
但题目要求是对于任意 \(x\) 都满足上述条件。那么如何构造一种满足条件的方案呢？
先考虑 \(n = 2^k\)，那么每个数都由 \(k\) 个互不相同的质数的乘积组成。我们设如果第 \(i\) 个数第 \(j\) 个质因子不等于第 \(1\) 个数第 \(j\) 个质因子，\(s_{i,j} = 1\)，否则 \(s_{i,j} = 0\)。那么可以得到 \(s_2 = 0000...01\)，\(s_3 = 0000...10\)，以此类推，\(s_n = 1111...11\)。
通过仔细观察，我们发现：如果字符串第 \(j\) 个字符为 1 时表示一个质数，为 0 时表示另一个质数，那么问题就能完美解决。因为这样每个 \(x\) 和其他数 \(y\) 的 \(\gcd\) 也能用上述的二进制字符串来表示，而 \(s_i\) 是两两不同的，那么所得的 \(\gcd\) 也是两两不同的。
如果 \(n \neq 2^k\)，我们设 \(m\) 为 \(> n\) 且能表示为 \(2^k\) 的最小的数，那么我们按照上述的方式构造出 \(m\) 个数，然后只输出前 \(n\) 个数就可以了。
但是构造的每个数不能超过 \(3 \times 10^{17}\)。为了让最大值尽可能小，将 \(s_{i,j} = 1\) 时乘上第 \(2 \times j - 1\) 个质数，否则乘上第 \(2 \times j\) 个质数。这样构造的好处在于比较小的质数都能得到充分利用。
这个做法是 \(73\) 分的，为什么？因为当 \(m = 4096\) 时，最后一个数略比 \(3 \times 10^{17}\) 大，会超。但是发现这距离题目要求 \(3 \times 10^{17}\) 差距不大，所以我们将构造的 \(m\) 个数从小到大排序，最后一个数的大小只有 \(2.91 \times 10^{17}\)，就能满足题目所给条件了。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#define int long long
#define lowbit(x) x&(-x)
using namespace std;
int n,w,a[2000005],b[2000005],y = 1;
struct node
{int fs[406];
}ed[4106];
bool cmp(node e,node f)
{__int128 x = 1,y = 1; for(int i = 1;i <= w;i ++){x *= (__int128)e.fs[i],y *= (__int128)f.fs[i];}return x < y;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0); cin >> n;w = ceil(log2(n));cout << w << endl;for(int i = 2;i <= 1000000;i ++)//取前2*n个质数{if(a[i] == 0)b[y ++] = i;for(int j = 1;i * b[j] <= 1000000 && j < y;j ++){a[i * b[j]] = 1;if(i % b[j] == 0)break;}}int dk = n;while(ceil(log2(dk)) != floor(log2(dk)))dk ++;for(int i = 1;i <= dk;i ++)for(int j = 1;j <= w;j ++){if((i >> (j - 1)) & 1)ed[i].fs[j] = b[j * 2 - 1];else ed[i].fs[j] = b[j * 2];}sort(ed + 1,ed + dk + 1,cmp);//按数的大小排序for(int i = 1;i <= n;i ++)//输出方案{cout << w << ' ';for(int j = 1;j <= w;j ++)cout << ed[i].fs[j] << " ";cout << '\n';}
}