AtCoder AGC #027 : D - Modulo Matrix

うーん、これはもうチョイ考えればよかった。
https://beta.atcoder.jp/contests/agc027/tasks/agc027_d

問題

以下の条件を満たすN*Nの行列を構築せよ。

• 各要素は互いに異なる10^15以下の正整数
• 隣接する２要素は、大きい方を小さい方で割るとその剰余は行列全体で一致する

解法

最大構成の500*500の行列を作ってしまえば、それ以下のNの解は含まれる。
500*500の行列の要素を、白黒で市松模様状に塗ったとする。
白いマスに小さな数字を入れていったとする。
黒いマスには、(上下左右の隣接マスのLCM)+1を入れるようにすれば、条件は満たせる。

あとは白いマスに相異なる小さい数字を入れつつ、黒マスに入れるLCMが10^15以下になるようにしたい。
r行c列において、まずr+cが一致するマスには同じ素数（異なるマスには異なる素数）を書き込む。
次に、r-cが一致するマスには同じ素数（異なるマスには異なる素数）を掛ける。

r+cは500通り、r-cも500通り程度あるので、合計1000通りほど素数があれば、これで白いマスに異なる値を書き込むことができる。
また、この時黒マスの値は上下左右に登場する４通りの素数の積+1となる。

1000番目の素数は7900ぐらいあるので、これを４つ掛けると10^15を超えてしまう。
よって大きな素数が近くに固まらないように配置するとよい。

ll N;
ll A[505][505];

const int prime_max = 1000000;
int NP,prime[100000],divp[prime_max];
map<int,int> M;

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

ll LCM(ll a,ll b) {
	if(a==0) return b;
	if(b==0) return a;
	return a/__gcd(a,b)*b;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	cprime();
	
	vector<int> P[2];
	FOR(i,500) {
		P[0].push_back(prime[i]);
		P[1].push_back(prime[999-i]);
	}
	
	FOR(y,500) FOR(x,500) if((x+y)%2==0) {
		i=(x+y)/2;
		j=(x-y)/2+249;
		A[y][x]=1LL*P[0][i]*P[1][j];
	}
	FOR(y,500) FOR(x,500) if((x+y)%2==1) {
		if(y) A[y][x]=LCM(A[y-1][x],A[y][x]);
		if(x) A[y][x]=LCM(A[y][x-1],A[y][x]);
		if(y<499) A[y][x]=LCM(A[y+1][x],A[y][x]);
		if(x<499) A[y][x]=LCM(A[y][x+1],A[y][x]);
		A[y][x]++;
	}
	
	
	FOR(y,N) {
		FOR(x,N) cout<<A[y][x]<<" ";
		cout<<endl;
	}
	
}

まとめ

うーん、残念。