CF1485D题解

· · 题解

题解思路：

直接构造确实很难，我们不妨这样想：

我们对一个 n 行 m 列的矩阵，对他黑白染色，那么我们发现一个黑点他上下左右都是白点，然后我们想办法让黑点是相同的值。

那么我们就可以取这 1 ~ 16 的 \operatorname{lcm} 就可以了，因为 1 \le a_{i,j} \le 16 所以他们的 \operatorname{lcm} 就不是很大。

那么黑色的数构造好了，就差白色点的。

那么白色点就可以：

a_{i,j} = \operatorname{lcm} - a_{i , j} ^ 4

AC CODE:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int gcd (int a , int b) {
    return b == 0 ? a : gcd (b , a % b);
}
ll res[20];
int main() {
    ll lcm = 1;
    for (int i = 1; i <= 16; ++ i) {//算lcm，也可以算出来以后直接用就可以了
        ll d = gcd (i , lcm);
        lcm = i / d * lcm;
    }
    for (int i = 1; i <= 20; ++ i) {//打表
        ll x = 1ll * i * i * i * i;//i ^ 4
        ll now = lcm + x;
        for (int j = 1; j <= 16; ++ i) 
            if (now % j == 0) 
                res[j] = now;//算白点的值
    }
    int n , m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= m; ++ j) {
            int x;
            cin >> x;
            if ((i + j) & 1) cout << lcm << ' ';//如果是黑点，那么就输出lcm
            else cout << res[x] << ' ';//否则就输出白点的值
        }
        cout << endl;//输出换行
    }
    return 0;//完结散花
}

码字不易，求赞！