前置知识：简要了解 CRT 和高斯消元
题意简述：给定一些系数，求 \(n\) 元线性同余方程组 \(A_i+\sum^{M}_{j=1}a_{i,j}x_j\equiv B_i(\mod 365)\) 的解。
注意到 \(365=5\times73\)，而且他们都是质数，这引导着我们思考先分别求出模 \(5,73\) 意义下的解，然后使用 CRT 来合并答案。
对固定的质数求解 \(n\) 元线性同余方程组的具体步骤，首先我们考虑把所有数字都放在模意义下，我们发现这个问题就变成了求解线性方程组的问题，用高斯消元法求解即可。
换言之：求解 \(n\) 元线性同余方程组，就是模意义下的高斯消元。
下面说一些实现细节。
- 1.我们读取日期的时候需要注意每个月的日子各不相同，开个数组存一下，然后我个人比较喜欢封装的写法，因此有了下面的代码：
int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int date() {
int d, m;
scanf("%d %d", &d, &m);
for (int i = 0; i < m - 1; ++i)
d += days[i];
return d - 1;
}
- 2.因为模数固定且质因子较少，我们直接手算式子就行。代码如下：
for (int i = 0; i < M; ++i) {
printf("%d\n", (146 * Sol5[i] + 220 * Sol73[i] + 364) % 365 + 1);
}
- 3.做除法的时候别忘了，其实是要乘以逆元的。
差不多就这些了，下面贴个代码：
#include <bits/stdc++.h>
using namespace std;
const int maxN = 205, maxM = 205;
int N, M;
int mts[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int Init[maxN][maxM + 1], tmp[maxN][maxM + 1];
int date() {
int d, m;
scanf("%d %d", &d, &m);
for (int i = 0; i < m - 1; ++i)
d += mts[i];
return d - 1;
}
int Sol5[maxM], Sol73[maxM], inv[100];
void get_inv(int p) {
inv[0] = 0;
for (int i = 1; i < p; ++i)
for (int j = 1; j < p; ++j)
if ((i * j) % p == 1)
inv[i] = j;
}
void Gauss(int p, int* Sol) {
for (int i = 0; i < N; ++i)
for (int j = 0; j <= M; ++j)
tmp[i][j] = Init[i][j] % p;
get_inv(p);
int valid = 0;
for (int s = 0; s < M; ++s) {
int ff = -1;
for (int i = valid; ff == -1 && i < N; ++i)
if (tmp[i][s] != 0)
ff = i;
if (ff == -1)
continue;
if (valid != ff)
for (int i = 0; i <= M; ++i)
swap(tmp[valid][i], tmp[ff][i]);
int rev = inv[tmp[valid][s]];
for (int i = 0; i <= M; ++i)
tmp[valid][i] = (tmp[valid][i] * rev) % p;
for (int i = 0; i < N; ++i)
if (i != valid) {
int cf = tmp[i][s];
for (int j = 0; j <= M; ++j) {
tmp[i][j] -= cf * tmp[valid][j];
tmp[i][j] %= p;
if (tmp[i][j] < 0)
tmp[i][j] += p;
}
}
++valid;
}
for (int i = 0; i < N; ++i) {
int first = -1;
for (int j = 0; j < M; ++j)
if (tmp[i][j] != 0) {
first = j;
break;
}
if (first == -1) {
if (tmp[i][M] != 0) {
cout << "-1\n";
exit(0);
}
continue;
}
Sol[first] = tmp[i][M];
}
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; ++i) {
int a = date(), b = date();
for (int j = 0; j < M; ++j)
scanf("%d", Init[i] + j);
Init[i][M] = ((b - a) % 365 + 365) % 365;
}
Gauss(5, Sol5);
Gauss(73, Sol73);
for (int i = 0; i < M; ++i) {
cout << (146 * Sol5[i] + 220 * Sol73[i] + 364) % 365 + 1 << "\n";
}
return 0;
}