agc027D

题目大意

题解

比较有趣的构造题，不难

首先如果按顺序放的话增长数是指数级别的，1e15绝对不行

把矩阵黑白染色，那么约束条件只存在不同颜色的格子之间，确定一种颜色之后另一种就是四个方向lcm+1

题解做法：把两个方向的对角线都分配一个质数，一个格子的值是两条对角线的积，这样一个格子是n^4*常数级别

我的做法：把棋盘分成2*2的格子，每个格子左上填x，右下填2x，那么一个要求的最多是n^6级别的，但是显然达不到，去重+大小间隔放后似乎可以比题解更优一些

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ll long long
//#define file
using namespace std;

int d[250001],n,i,j,k,l,l1,l2,x,y,t;
ll a[501][501],mx,s;
map<ll,bool> mp;
bool bz[1000001];

ll gcd(ll x,ll y) {ll r=x%y; while (r) x=y,y=r,r=x%y; return y;}
ll lcm(ll x,ll y) {ll s=gcd(x,y);return (x/s)*(y/s)*s;}

int main()
{
	#ifdef file
	freopen("agc027d.in","r",stdin);
	freopen("agc027d.out","w",stdout);
	#endif
	
	scanf("%d",&n),s=((n+1)/2)*((n+1)/2);
	i=2;
	while (t<s)
	{
		if (!bz[i] && !bz[i*2]) d[++t]=i,bz[i]=bz[i*2]=1;
		++i;
	}
	l1=0,l2=t+1;
	fo(i,1,n)
	{
		fo(j,1,n)
		if ((i&1) && (j&1))
		{
			if (((i+j)/2)&1)
			{
				++l1;
				a[i][j]=d[l1];
				if (i<n && j<n)
				a[i+1][j+1]=d[l1]*2;
			}
			else
			{
				--l2;
				a[i][j]=d[l2];
				if (i<n && j<n)
				a[i+1][j+1]=d[l2]*2;
			}
		}
	}
	fo(i,1,n) fo(j,1,n) if (a[i][j]) mp[a[i][j]]=1;
	
	mx=0;
	fo(i,1,n)
	{
		fo(j,1,n)
		if (!a[i][j])
		{
			a[i][j]=1;
			if (i>1) a[i][j]=lcm(a[i][j],a[i-1][j]);
			if (i<n) a[i][j]=lcm(a[i][j],a[i+1][j]);
			if (j>1) a[i][j]=lcm(a[i][j],a[i][j-1]);
			if (j<n) a[i][j]=lcm(a[i][j],a[i][j+1]);
			
			s=a[i][j],++a[i][j];
			while (mp[a[i][j]]) a[i][j]+=s;
			mp[a[i][j]]=1;
			mx=max(mx,a[i][j]);
		}
	}
	fo(i,1,n)
	{
		fo(j,1,n)
		printf("%lld ",a[i][j]);
		printf("
");
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}