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

题意

题目链接

构造一个$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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1225 八数码难题

1225 八数码难题  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Descri...

29140
来自专栏nummy

Uninformed search Python实现【译】

图的搜索可以分为uninformed搜索和informed搜索,两者的区别是前者是的搜索是盲目的,它不知道目标节点在哪,而后者是启发式的搜索。

15020
来自专栏人工智能LeadAI

Python 中argparse模块的使用

如果脚本很简单或临时使用,没有多个复杂的参数选项,可以直接利用sys.argv将脚本后的参数依次读取(读进来的默认是字符串格式)。

10640
来自专栏后端技术探索

(答案来了)两道腾讯面试题目

前天推送的文章《两道腾讯技术面试题(二面经历)》,收到了不少留言,感兴趣的可以去哪篇文章下查看精选留言,有一多半同学没有正确理解题目,可分享的留言寥寥无几,根据...

12310
来自专栏ACM小冰成长之路

HDU-6249-Alice’s Stamps

ACM模版 描述 ? 题解 DPDP 问题,设 dp[i][j]dp[i][j] 表示前 ii 个位置选取 jj 个区间的最优解。当然 ii 要加以处理,因为我...

27070
来自专栏尾尾部落

[LeetCode]Palindrome Number回文

链接:https://leetcode.com/problems/palindrome-number/#/description 难度:Easy 题目:De...

13220
来自专栏数据结构与算法

2018.7.21NOIP模拟赛?解题报告

那么我们还需要对每个已经加入的右括号维护一个小根堆。每次判断是否替换掉更小的会更优

9050
来自专栏数据处理

proc-tabulate

12220
来自专栏数据结构与算法

洛谷P4013 数字梯形问题(费用流)

梯形的第一行有 mmm 个数字。从梯形的顶部的 mmm 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。

13040
来自专栏图形学与OpenGL

5.5 Opengl编程实例-红蓝三角形

21620

扫码关注云+社区

领取腾讯云代金券