[AGC027D] Modulo Matrix 题解

题意：

构造一个 \(N\times N\) 的矩阵. 要求：

所有元素 \(a_{i,j}\) 互不相同。

满足 \(1\le a_{i,j}\leq 10^{15}\)。

对于任意相邻（上下左右）的数字，\(\max(x,y)\bmod \min(x,y)\) 都相等，且均为正整数。

可以证明方案一定存在。

数据范围：

\(2 \le N \le 500\) 。

简单跑一跑暴力就会发现符合条件的情况还是很多的

容易想到一种构造，如果 \((i + j) \bmod 2=0\) ，就比较随便的填一个数

否则填周围四个相邻格子的最小公倍数 \(+1\) ，即 \(a_{i,j} = \operatorname{lcm}\left(a_{i-1, j}, a_{i, j-1}, a_{i+1, j}, a_{i, j+1}\right)+1\)

这样子随便搞的话值域大约为 \(\mathcal{O}(n^8)\) ，过不了。

注意到 \(\operatorname{lcm}(a,b,c,d)\) 的大小不仅与运算的 \(a,b,c,d\) 的数量级有关，还与他们的 \(\gcd\) 有关

考虑最大化 \(\gcd\) 以降低 \(\operatorname{lcm}(a,b,c,d)\) 的数量级，注意这里不是 \(\gcd(a,b,c,d)\) ，是相邻两个的 \(\gcd\) 。

容易想到令 \(a_{i,j} = p_{i-j}\times q_{i + j}\) ，其中 \(p,q\) 均为质数。

注意要调整一下质数的顺序，这样 \(\operatorname{lcm}\) 约为 \(\mathcal{O}\left((n \ln n)^4\right)\) ，具体构造如下：

~~不要问我怎么想到这么构造的，我反正想不出来~~，但是这个构造确实很牛批。

时间复杂度 \(\mathcal{O}(n^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))

char vis[N];
int pcnt, a[N], b[N], p[N];
void init(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i]) p[++pcnt] = i;
        for(int j = 1; j <= pcnt && i * p[j] <= n; j++) {
            vis[i * p[j]] = true; if(i % p[j] == 0) break;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    init(114514); int n; cin >> n;
    rep(i, 1, n) a[i] = p[(i & 1) ? i / 2 + 1 : n + n - i / 2 + 1];
    rep(i, 1, n) b[i] = p[((i & 1) ? n - i / 2 : n + i / 2) + (n & 1)];
    a[0] = a[n + 1] = b[0] = b[n + 1] = 1;
    rep(i, 1, n) rep(j, 1, n)
    {
        if((i + j) & 1)
        {
            const int _1 = a[(i + j) / 2] * a[(i + j) / 2 + 1];
            const int _2 = b[(n + i - j + (n & 1)) / 2] * b[(n + i - j + (n & 1)) / 2 + 1];
            cout <<  _1 * _2 + 1 << " \n"[j == n];
        }else { cout << a[(i + j) / 2] * b[(n + i - j + (n & 1)) / 2] << " \n"[j == n]; }
    }
    return 0;
}