2020牛客暑期多校训练营（第六场）G-Grid Coloring

题目大意

给定一个n×n的正方形（如下图），有k种不同颜色，给每条边染色，使其满足以下条件，输出一种方案：
(1) 所有颜色的边数应该相同；
(2) 不存在一个单色环；
(3) 一行或一列至少存在两种颜色。

解题思路

图片转载自：https://www.cnblogs.com/st1vdy/p/13387806.html

最开始，我们要排除出掉没有解决方案的三种情况: $n=1,k=1,2n(n+1)\space mod\space k\neq0$ （边数mod颜色数）

接着，我们按这样的方式给每条边标号：
图片说明

对于一个1×1的环（图中橙色框），它的两条纵边序号相邻，颜色应该不同；
对于一个A×B,A<B的环（图中绿色框），它必定有相邻的横边，因此染的颜色不同；同理可以证明所有横边均不同色。
对于一个A×B,A>B的环（图中紫色框），如果其横边长为1，那么它必定有相邻的纵边；
如果其横边长>1，那么它必定有相邻的横边。

这样能得出什么结论？
可以发现，因为任意一个环以及任意横边均不同色，因此我们只需要分析纵边是否同色。

从我们标完号的图中，我们可以发现，两条相邻（纵向）边的序号差是2n+1。如图中第一列n+1,3n+2,5n+3......
因为 $gcd(k,2n+1)=1$ （2n+1不能是一个循环节（k）的倍数）且 $k|2n(n-1)$ ，
所以我们可以得出 $gcd(2n(n+1),2n+1)=1$ 。继续推导：
图片说明
所以相邻的纵边不同色。

那么涂色的方案已经呼之欲出了：
我们按照上图中边的标号（也就是从上到下），每n个为一组，每组按顺序涂颜色1到k。（即序号为1的颜色1，序号为2的颜色2……序号为k的颜色k，序号为k+1的颜色1，序号为k+2的颜色2……）

AC代码

#include<bits/stdc++.h>
using namespace std;
int a[210][210],b[210][210];
int main()
{
    int T,n,k,t,i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        if(n==1 || k==1 || (2*n*(n+1))%k)
        {
            puts("-1");
            continue;
        }
        t=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
                t=t%k+1,a[i][j]=t;
            for(j=0;j<=n;j++)
                t=t%k+1,b[j][i]=t;
        }
        for(i=0;i<n;i++)
            t=t%k+1,a[n][i]=t;
        for(i=0;i<=n;i++)
        {
            for(j=0;j<n;j++)
                printf("%d ",a[i][j]);
            puts("");
        }
        for(i=0;i<=n;i++)
        {
            for(j=0;j<n;j++)
                printf("%d ",b[i][j]);
            puts("");
        }
    }
    return 0;
}