当前位置： 移动技术网 > IT编程>开发语言>C/C++ > agc027D - Modulo Matrix(构造 黑白染色)

agc027D - Modulo Matrix(构造 黑白染色)

2018年09月28日  | 移动技术网IT编程  | 我要评论

kbs超级中国第五集,上海站火车时刻表,3jp电影下载

题意

构造一个$n * n$的矩阵，要求任意相邻的两个数$a,b$,使得$max(a,b) % min(a,b) \not = 0$

sol

我的思路：

假设$mod = 1$，那么可以在第一行放2 3 4 5 $\dots$，第一列同理也这样放

对于任意位置$i$，一定满足要求的一个数是a[i - 1][j] * a[i][j - 1] / __gcd(a[i - 1][j], a[i][j - 1]) + 1

然而最后的数大到上天啊。。。

标算挺巧妙的，首先把整个图黑白染色，那么同色点之间是互不影响的。

考虑构造$mod = 1$的矩阵。

若白点的权值确定了，那么黑点的权值应当是所有相邻白点的$lcm$+1，

那所有白点的权值怎么确定呢？

考虑直接用素数填充对于正对角线和负对角线上的每个点分配一个不同的素数

那么任意白点的权值为所在正对角线上的素数 乘 负对角线的素数

这样算出来最大的$a_{ij} = 414556486388264 $，满足要求

不过为啥数组要开1000才能过???

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn = 1e5 + 10;
int n;
int a[1001][1001], vis[maxn], prime[maxn], tot;
void getphi() {
    vis[1] = 1;
    for(int i = 2; i; i++) {
        if(!vis[i]) prime[++tot] = i;
        if(tot == 1000) break; 
        for(int j = 1; j <= tot && (i * prime[j] <= 10000); j++) {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j])) break;
        }
    }
}
int lcm(int x, int y) {
    if(x == 0 || y == 0) return x + y;
    return x / __gcd(x, y) * y;
}
main() {
    getphi();
    cin >> n;
    if(n == 2) {
        printf("4 7\n23 10");
        return 0;
    }
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= n; j++)
            if(!((i + j) & 1)) a[i][j] = prime[(i + j) / 2] * prime[n + (i - j) / 2 + (n + 1) / 2];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(!a[i][j]) 
                a[i][j] = lcm(lcm(a[i - 1][j], a[i][j - 1]), lcm(a[i][j + 1], a[i + 1][j])) + 1;
    for(int i = 1; i <= n; i++, puts(""))
        for(int j = 1; j <= n; j++)
            cout << a[i][j] << " ";
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网