构造、数学、最大公约数与最小公倍数

题目链接

必有其败因。

题目要求填完数字后第 $i$ 行所有数字的 $\gcd$ 等于第 $i$ 列所有数字的 $\gcd$，并且每行的数不少于 $2$ 个，每列的数不少于 $2$ 个。

考虑只用 $2n$ 个数让每行每列的 $\gcd$ 都变成 $1$，这样 $k > 2n$ 时可以随意放置比 $2n$ 大的数字。

初始思路如下，使用如下构造处理每两行两列，表格中 $i \equiv 1 (\bmod 4)$，这个构造方案需要处理 $\gcd(i,i+3)=3$ 的问题，我没有找到可行的解决办法。另外 $n$ 为奇数的情况我还没想。

到这时候应该推翻做法了，而不是修修补补的。

下面是队友 Trainer_Marvin 给出的构造方案，这个例子里 $n=4$。这个方案很好地利用了 $\gcd(i,i+1)=1$ 的性质，同时还利用了 $\gcd(1,x)=1$ 的性质。

斜向放置奇数，在奇数下面放置偶数，将 $2n$ 放在右上角即可完成，其余数字可以随意摆放，时间复杂度 $O(k \log k)$。

#include<bits/stdc++.h>
using namespace std;
pair<int,int> ans[1'000'005];
set<pair<int,int>> s;
int n,k,cnt;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n*2;i+=2) ans[i]=make_pair(i/2+1,i/2+1);
    for(int i=2;i<=n*2;i+=2) ans[i]=ans[i-1],++ans[i].first;
    cnt=n*2,ans[n*2]=make_pair(1,n);
    for(int i=1;i<=n*2;i++) s.emplace(ans[i]);
    if(cnt!=k) for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) if(!s.count(make_pair(i,j))){
            ans[++cnt]=make_pair(i,j);
            if(cnt==k) goto printans;
        }
    printans:
    for(int i=1;i<=k;i++) printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}