题目

试构造一个 $n\times n$ 的矩阵,使得任意相邻的两个数 $x,y$ 有 $\max \{x,y\}\bmod \min \{x,y\}$ 相同。

你需要保证矩阵中的元素均不超过 $10^{15}$.

分析

考虑进行棋盘的黑白染色,在黑点放最大值,白点放最小值,这样我们先放白点,再放黑点为与其相邻的数的 $\operatorname{lcm} + 1$ 就好了。

问题是这样放的数太大了,考虑在矩阵的所有对角线($i+j,i-j$ 相同的若干类点)填上一个质数,然后令对角线的白交点填上对角线的乘积,这样可以发现黑点为四个质数之积,就可以压到 $10^{15}$ 以内了。

代码

const int kN = 1e3 + 5, kP = 1e5 + 5, kInf = 0x3f3f3f3f;

ll Gcd(ll a, ll b) {
    return b ? Gcd(b, a % b) : a;
}
ll Lcm(ll a, ll b) {
    return a / Gcd(a, b) * b;
}

int p[kP], cnt = 0;
bool flag[kP];
void Sieve() {
    for(int i = 2; i < kP; ++i) {
        if(!flag[i])
            p[++cnt] = i;
        for(int j = 1; j <= cnt && i * p[j] < kP; ++j) {
            flag[i * p[j]] = true;
            if(i % p[j] == 0) break;
        }
    }
}

int n, usd_p = 0; ll A[kN][kN];
std::map <int, int> usd_p_a, usd_p_b;

int main() { 
    int T = 1; //rd(T);
    while(T--) {
        Sieve();
        rd(n);
        if(n == 2) {
            printf("4 7\n23 10\n");
            return 0;
        }
        for(int i = 0; i <= n + 1; ++i)    
            for(int j = 0; j <= n + 1; ++j) 
                A[i][j] = 1;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j) if((i + j) % 2 == 0) {
                if(!usd_p_a.count(i + j))
                    usd_p_a[i + j] = ++usd_p;
                A[i][j] *= p[usd_p_a[i + j]];
            }
        for(int i = n; i; --i)
            for(int j = n; j; --j) if((i + j) % 2 == 0) {
                if(!usd_p_b.count(i - j))
                    usd_p_b[i - j] = ++usd_p;
                A[i][j] *= p[usd_p_b[i - j]];
            }
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j) if((i + j) % 2 != 0) {
                A[i][j] = Lcm(Lcm(A[i + 1][j], A[i][j + 1]), Lcm(A[i - 1][j], A[i][j - 1])) + 1;
            }
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j)
                printf("%lld ", A[i][j]);
            printf("\n");
        }
    } return 0;
}
最后修改:2021 年 02 月 05 日 08 : 53 PM