P5185 题解

Piggy343288 · 2023-05-02 13:09:04 · 题解

前置知识：简要了解 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;
}