[CF1485D] Multiples and Power Differences

[CF1485D] Multiples and Power Differences - 构造

Description

有一个矩阵 (a) ,请你构造一个矩阵 (b) ，使得：(0 < b_{i,j}le 10^6),(b_{i,j}) 是 (a_{i,j}) 的倍数,(b) 中相邻的两个数的差的绝对值可以写成 (k^4(kinmathbb{N}^+)),(1le a_{i,j}le 16)

Solution

设 x=LCM(1,2,3,...,14,15,16)，那么对任意 aij=a, (a|(x-a^4))

黑白染色，一类填 x，一类填 (x-a_{ij}^4)

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n + 2, vector<int>(m + 2));
    int x = 1;
    for (int i = 1; i <= 16; i++)
        x = x * i / __gcd(x, i);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if ((i + j) & 1)
                cout << x - pow(a[i][j], 4) << " ";
            else
                cout << x << " ";
        }
        cout << endl;
    }
}