[ARC140E]Not Equal Rectangle
做题时间：2022.8.11
\(【题目描述】\)
给定 \(N,M(2\leq N,M\leq 500)\)，构造一个大小为 \(N\times M\) 的矩阵 \(a_{i,j}\)，满足 \(1\leq a_{i,j}\leq 25\) ，且对于任意 \(1\leq x1,x_2\leq N\) 和 \(1\leq y_1,y_2\leq M\)，不存在 \(a_{x_1,y_1}=a_{x_1,y_2}=a_{x_2,y_1}=a_{x_2,y_2}\)
\(【输入格式】\)
一行两个整数表示 \(N,M\)
\(【输出格式】\)
一个 \(N\times M\) 的矩阵
\(【考点】\)
数学
\(【做法】\)
发现 \(\sqrt n\approx 25\) 启发我们用分块思想。
若我们将一个 \(p^2\times p^2\) 的大矩阵分割成 \(p^2\) 个 \(p\times p\) 的小矩阵，并且对于每一个小矩阵，从第一行开始，用 \([1,2,...,p]\) 循环放置，得到：
\[P_1= \begin{pmatrix} 1 & 2 & \cdots & p-1 & p \\ 2 & 3 & \cdots & p & 1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ p-1 & p & \cdots & p-3 & p-2 \\ p & 1 & \cdots & p-2 & p-1 \\ \end{pmatrix} \\ P_2= \begin{pmatrix} 2 & 3 & \cdots & p & 1 \\ 3 & 4 & \cdots & 1 & 2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ p & 1 & \cdots & p-2 & p-1 \\ 1 & 2 & \cdots & p-1 & p \\ \end{pmatrix} \\ \vdots \\ P_p= \begin{pmatrix} p & 1 & \cdots & p-2 & p-1 \\ 1 & 2 & \cdots & p-1 & p \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ p-2 & p-1 & \cdots & p-4 & p-3 \\ p-1 & p & \cdots & p-3 & p-2 \\ \end{pmatrix} \\ \]\[A= \begin{pmatrix} P_1 & P_1 & \cdots & P_1 & P_1 \\ P_1 & P_2 & \cdots & P_{p-1} & P_p \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ P_1 & P_{p-1} & \cdots & P_{p-4} & P_{p-3} \\ P_1 & P_p & \cdots & P_{p-3} & P_{p-2} \\ \end{pmatrix} \]这个方法同样可以扩展到 \(N\times M\) 的矩阵，即找到一个 \(p\) ，满足 \(p^2\geq\max(n,m)\) 且 \(p\) 是质数。 \(23\) 是最合适的选择。
可以得到：
\[A_{i,j}=((\lfloor i/p \rfloor \cdot \lfloor j/p \rfloor+i+j) \mod p)+1$$ ，其中 $p=23$ $【代码】$ ```cpp #include<cstdio> #include<iomanip> #include<cmath> using namespace std; int n,m; int main() { scanf("%d%d",&n,&m); int p=23; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ printf("%d ",((i/p)*(j/p)+i+j)%p+1); } printf("\n"); } return 0; } ```\] 标签：矩阵,Equal,times,leq,cdots,pmatrix,ARC140E,Rectangle,vdots From： https://www.cnblogs.com/Unlimited-Chan/p/16740959.html