「AGC027D」Modulo Matrix

「AGC027D」Modulo Matrix

传送门

神仙构造题。

首先考虑一个非常自然的思路，我们把棋盘黑白染色后会变成一个二分图，黑色棋子只会与白色棋子相邻。

也就是说，我们可以将二分图的一部随便填数，另一部分填上黑色数的乘积加上某个余数即可。

需要注意随便填数的一部的所有数必须大于这个选择的余数。

然后你发现过不了，这样的数的大小期望最大值大概是 ((frac{n^2}{2})^4)。

然后我们可以考虑给每一个对角线（每一行、每一列应该也行？）设一个权值 (x)，然后随便填数的部分的值等于对应两条对角线上的值的乘积。

为了保证不重复，我们可以使用质数。

这样感觉就非常对了。

/*---Author:HenryHuang---*/
/*---Never Settle---*/
#include<bits/stdc++.h>
using namespace std;
const long long maxn=2e6+5;
long long pri[maxn],p[maxn],cnt;
void init(){
	for(long long i=2;i<=2e6;++i){
		if(!p[i]) pri[++cnt]=i;
		for(long long j=1;j<=cnt&&i*pri[j]<=2e6;++j){
			p[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}
long long a[505][505];
long long nx[]={0,0,1,-1};
long long ny[]={1,-1,0,0};
long long gcd(long long a,long long b){
	if(!b) return a;
	return gcd(b,a%b);
}
map<long long,int> s;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	long long n;cin>>n;
	init();
	for(int i=1;i<=n;++i){
		for (int j=((i+1)&1)+1;j<=n;j+=2){
			a[i][j]=pri[(i+j)/2]*pri[n+(i-j)/2+(n+1)/2];
		}
	}
	for(long long i=1;i<=n;++i){
		for(long long j=1;j<=n;++j){
			if(((i+j)&1)==1){
				long long lcm=0;
				for(long long k=0;k<4;++k){
					if((!lcm)&&a[i-nx[k]][j-ny[k]]){
						lcm=a[i-nx[k]][j-ny[k]];
					}
					else if(a[i-nx[k]][j-ny[k]]){
						lcm=1ll*lcm/gcd(lcm,a[i-nx[k]][j-ny[k]])*a[i-nx[k]][j-ny[k]];
					}
				}
				long long tmp=lcm;
				while(s[tmp+1]) tmp+=lcm;
				a[i][j]=tmp+1; s[tmp+1]=1;
			}
			cout<<a[i][j]<<' ';
		}
		cout<<'
';
	}
	return 0;
}