Modulo Matrix [AtCoder Grand Contest 027 D]

https://beta.atcoder.jp/contests/agc027/tasks/agc027_d

解法

https://beta.atcoder.jp/contests/agc027/submissions/3208300

公式解説放送を見ましょう。
動画を見れば、考え方はそんなに難しくない。
実装方法について説明する。
　
まずN=2のときは数が被ってしまうので、サンプルケース通りに答えておこう。
　
minをまず確定するが、(x+y)%2==0の所にminを入れていく。
斜めに素数を割り当てていくというのを実装するにはx+y,x-yを使うといい。
x+yで／の向きの斜めを特定できる。x-yで＼の向きの斜めを特定できる。
x+y,x-y共に偶数であるので、2で割って圧縮しよう。
u = (x+y)/2
v = (x-y)/2
これで良さそうだが、このままだとvが-N/2からN/2まで取りうるので、N/2を足して0以上にしておこう。
（下の解法では一応、ちゃんと0以上になるように+1している）
uもvも最大500通りあるので、素数を1000個ほど用意して、それぞれ割り当てる。
「vp[i] := i番目の素数」とすると、uにはvp[u]、vにはvp[1010-v]を割り当てることにする。
1010は適当です。
これで後は、かけて入れるだけ。
　
maxは周りのlcmを取るだけ。
特に注意点なし。

int N;
ll ans[505][505];
//---------------------------------------------------------------------------------------------------
void _main() {
    auto vp = makePrimes(51010);
    cin >> N;
 
    if (N == 2) {
        printf("4 7\n23 10\n");
        return;
    }
 
    rep(y, 0, N) rep(x, 0, N) if ((x + y) % 2 == 0) {
        int u = (x + y) / 2;
        int v = (x - y) / 2 + N / 2 + 1;
 
        ans[y][x] = 1LL * vp[u] * vp[1010 - v];
    }
 
    rep(y, 0, N) rep(x, 0, N) if ((x + y) % 2 == 1) {
        ll c = 1;
        if (0 <= y - 1) c = lcm(c, ans[y - 1][x]);
        if (y + 1 < N) c = lcm(c, ans[y + 1][x]);
        if (0 <= x - 1) c = lcm(c, ans[y][x - 1]);
        if (x + 1 < N) c = lcm(c, ans[y][x + 1]);
        ans[y][x] = c + 1;
    }
 
    rep(y, 0, N) {
        rep(x, 0, N) {
            if (x) printf(" ");
            printf("%lld", ans[y][x]);
        }
        printf("\n");
    }
}