Codeforces Round #678 (Div. 2)B. Prime Square(矩阵均匀构造)

地址：http://codeforces.com/contest/1436/problem/B

题意：

输出一个n*n的矩阵，只包含非素数，而且每行，每列的和为素数

解析：

先让矩阵所有元素为1

n是素数的话，直接输出即可。

否则，找出n之前的第一个合数，求出差cha

这个cha，就是每行需要几个1变成0。

然后均匀放0即可，具体见代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
char a[maxn];
bool check(int x)
{
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int mp[111][111];
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                mp[i][j]=1;
        }
        if(check(n))
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                    cout<<"1 ";
                    cout<<endl;
            }
        }
        else
        {
            int md;
            for(int i=n-1;i>=2;i--)
            {
                if(check(i))
                {
                    md=i;
                    break;    
                }    
            }
            int cha=n-md;
            int j=1;
            int cnt=1;
            for(int i=1;i<=cha;i++)
            {
                j=cnt;
                for(int c=1;c<=n;c++)
                {
                    mp[c][j]=0;
                    j++;
                    if(j==n+1)
                        j=1;
                }
                cnt++;
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                    cout<<mp[i][j]<<" ";
                    cout<<endl;
            }            
        }
    }

}