[Số học] [Tô màu bàn cờ] [Number Theory] [Chessboard Coloring] [AtCoder] AGC027-D Modulo Matrix

Đề bài

Tóm tắt đề bài

Tạo bảng kích thước n*n sao cho các số trong bảng đôi một khác nhau và với mọi hai số (x,y) kề cạnh, ta có max(x,y)%min(x,y) = m với m là hai số nguyên dương nào đó. Ngoài ra, các số trong bảng không được vượt quá 10^15.

Ý tưởng

Tô màu kiểu bàn cờ cho bảng, sau đó điền hết ô đen với các số bất kì, khi đó số ở ô trắng sẽ bằng bội chung lớn nhất của các ô đen kề với nó + 1.

Lời giải

Để đảm bảo các số trong bảng đôi một khác nhau, với mỗi đường chéo đen chính và đường chéo đen phụ, ta gán với đường chéo đó một số nguyên tố khác nhau. Mỗi ô đen sẽ có giá trị bằng tích của hai số nguyên tố được gán với hai đường chéo đi qua ô đó. Khi đó, số ở ô trắng sẽ bằng tích của bốn số nguyên tố nguyên tố của bốn đường chéo đen giáp với nó cộng 1. Dễ dàng nhận thấy rằng số ở các ô là khác nhau.

(Lưu ý ta gán số nguyên tố cho cả những đường chéo nằm ngoài bảng để đảm bảo các ô trắng ở mép không bị trùng nhau)

Ta thấy trong trường hợp xấu nhất (n = 500), ta chỉ có khoảng 1000 đường chéo đen. Do số nguyên tố thứ 1000 bằng 7919, ta thấy chỉ cần gán số nguyên tố sao cho các đường chéo chính có số nguyên tố nhỏ sẽ giáp với các đường chéo phụ có số nguyên tố lớn là hoàn toàn có thể thỏa mãn được điều kiện các số trong bảng không vượt quá 10^15.

Code (Java)