目录

[TOC]

题目链接

题解

从第左上角第一个点开始染色，相邻不同色，染法唯一

那么一个点的四周与他不同色，我们另这个点比四周都大，那么这个点权值可以使lcm(四周的点权值)+1

于是我们就得到了一种构造方案，染色后对一种颜色的点进行赋值，然后另一种颜色的点取lcm

可是....直接这样瞎构造会爆掉1e15

对于一种染色点，可以按照i + j和i - j分为两类,每一类乘上一个相同的质数

对于当前格子的价值就是从左上角到右下角，和从右上角到左下角穿过他的第k素数乘积

这样构造的lcm最大就是四个素数(prime[n],prime[n - 1],prime[2 * n],prime[2 * n - 1])的乘积

不会超过1e15

代码

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#define gc getchar()

#define pc putchar

#define LL long long

inline int read() {

	int x = 0,f = 1;

	char c = getchar();

	while(c < '0' || c > '9') c = gc;

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

	return x * f;

}

void print(LL x) {

	if(x < 0) {

		pc('-');

		x = -x;

	}

	if(x >= 10) print(x / 10);

	pc(x % 10 + '0');

}

const int maxn = 20007;

int n;

int prime[maxn];

bool vis[maxn];

void pre(int lim = 10000) {

	for(int cnt = 0,i = 2;i <= lim;++ i) {

		if(!vis[i]) prime[++ cnt] = i;

		for(int j = 1;j <= cnt && prime[j] * i <= lim;++ j) {

			vis[i * prime[j]] = 1;

			if(i % prime[j] == 0) break;

		}

	}

}

LL a[507][507];

LL gcd(LL x,LL y) {

	return y == 0 ? x : gcd(y,x % y);

}

LL lcm(LL x,LL y) {

	return x / gcd(x,y) * y;

}

int main() {

	n = read();

	pre();

	if(n == 2) {

		pc('4');pc(' ');pc('7');pc('\n');

		print(23);pc(' '); print(10); pc('\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((j & 1) == (i & 1)) {

				a[i][j] = prime[(i + j) / 2] * prime[(i + n + 1 - j) / 2 + n];

				a[i + 1][j] = lcm(a[i + 1][j],a[i][j]);

				a[i - 1][j] = lcm(a[i - 1][j],a[i][j]);

				a[i][j + 1] = lcm(a[i][j + 1],a[i][j]);

				a[i][j - 1] = lcm(a[i][j - 1],a[i][j]);

			}

		}

	for(int i = 1;i <= n;++ i)

		for(int j = 1;j <= n;++ j)

			if((i & 1) == (j & 1));

			else a[i][j] ++;

	for(int i = 1;i <= n;++ i,pc('\n'))

		for(int j = 1;j <= n;++ j)

			print(a[i][j]),pc(' ');

	return 0;

}

巴特西

AGC027 D - Modulo Matrix 构造

目录

[TOC]

题目链接

题解

代码

最新文章

热门文章

巴特西

AGC027 D - Modulo Matrix 构造

目录 [TOC]

题目链接

题解

代码

最新文章

热门文章

目录

[TOC]