CF1734E Rectangular Congruence 题解

FFTotoro · 2022-10-16 12:56:42 · 题解

本题需要使用一些数论的特殊性质。

观察题目的第二个条件，如果我们不看第一个条件的话，可以构造出一个矩阵 A，其中 a_{i,j}=i\times j\pmod n，满足第二个条件。

赛后看了 CF 官方题解，里面阐述了一个定理：只要 a_{i,j} 满足 ai^2+bij+cj^2+di+ej+f 的形式（a,b,c,d,e,f 是整数），且 b\not\equiv 0\pmod n，那么这样的矩阵 A 就是满足条件的。所以我们前面的方法是正确的，这个定理的证明可参考 CF 官方题解。

现在我们再来考虑第一个条件。实现之前，先要明白——如果一个矩阵满足第二个条件，那么给其中的某一行或某一列中的全部元素都加上一个定值，那么第二条件仍然成立。

到这里解法已经呼之欲出了：对于 i=1,2,\ldots,n，给第 i 行的每一个元素都加上 b_i-a_{i,i}，即可满足两个条件。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector a(n,vector<int>(n));
  vector<int> b(n);
  for(auto &i:b)cin>>i;
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      a[i][j]=i*j%n; // 构造初始矩阵
  for(int i=0;i<n;i++){
    int x=(b[i]-a[i][i]+n)%n; // 经典模加模
    for(int j=0;j<n;j++)
      (a[i][j]+=x)%=n; // 给每一个元素加上差值
  }
  for(int i=0;i<n;i++,cout<<'\n')
    for(int j=0;j<n;j++)cout<<a[i][j]<<' ';
  return 0;
}