题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2827

题解:

一开始直接高斯消元,然后一直wa,接着我改了逆元进去,还是各种wa。

然后把P分成多个1000到10000的Pi才过的。

这是一道同时包含高斯消元、扩展欧几里得(逆元)、中国剩余定理的模板题。

/*
 * Author: Haipz
 * School: HDU
 * File Name: 2827.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

/*
const int N = 100;
int a[N + 5][N + 5], x[N + 5], PN;
bool free_x[N + 5];

int gcd(int a, int b) {
    if (b) return gcd(b, a % b);
    return a;
}

int lcm(int a, int b) {
    return a/gcd(a, b)*b;
}

int Gauss(int equ, int var) {
    memset(x, 0, sizeof(x));
    memset(free_x, true, sizeof(free_x));
    int k, col, free_x_num = 0;
    for (k = col = 0; k < equ && col < var; ++k, ++ col) {
        int max_k = k;
        for (int i = k + 1; i < equ; ++i)
            if (abs(a[i][col]) > abs(a[max_k][col])) max_k = i;
        if (max_k != k)
            for (int i = k; i < var + 1; ++i) swap(a[k][i], a[max_k][i]);
        if (a[k][col] == 0) {
            --k;
            continue;
        }
        for (int i = k + 1; i < equ; ++i)
            if (a[k][col] != 0) {
                int t = lcm(a[i][col], a[k][col]);
                int ta = t/a[i][col], tb = t/a[k][col];
                for (int j = col; j < var + 1; ++j) a[i][j] = a[i][j]*ta - a[k][j]*tb;
            }
    }
    for (int i = k; i < equ; ++i)
        if (a[i][col] != 0) return -1;
    if (k < var) {
        for (int i = k - 1; i >= 0; --i) {
            int free_index;
            for (int j = 0; j < var; ++j)
                if (a[i][j] != 0 && free_x[j]) ++free_x_num, free_index = j;
            if (free_x_num > 1) continue;
            int t = a[i][var];
            for (int j = 0; j < var; ++j)
                if (a[i][j] != 0 && j != free_index) t -= a[i][j]*x[j];
            x[free_index] = t/a[i][free_index];
            free_x[free_index] = false;
        }
        return var - k;
    }
    for (int i = var - 1; i >= 0; --i) {
        int t = a[i][var];
        for (int j = i + 1; j < var; ++j)
            if (a[i][j] != 0) t -= a[i][j]*x[j];
        if (t % a[i][i] != 0) return -2;
        x[i] = t/a[i][i];
    }
    return 0;
}
*/

/*
const int N = 100;
const double eps = 1e-9;
double *E[N + 5];
int at[N + 5];

int Gauss(int n, int m) {
    int r = 0, c = 0;
    while (r <= n && c < m) {
        if (fabs(E[r][c]) < eps) {
                for (int i = r + 1; i <= n; ++i)
                    if (fabs(E[i][c]) >= eps) swap(E[i], E[r]);
                if (fabs(E[r][c]) < eps) {
                    ++c;
                    continue;
                }
        }
        double t = E[r][c];
        for (int j = c; j <= m; ++j) E[r][j] /= t;
        for (int i = 0; i <= n; ++i)
            if (i != r && fabs(E[i][c]) >= eps) {
                double g = E[i][c];
                for (int j = c; j <= m; ++j) E[i][j] -= g*E[r][j];
            }
        at[c] = r, ++r, ++c;
    }
    return r;
}
*/

#define LL long long
const int N = 100, P = 10000;
LL a[N + 5][N + 5], b[N + 5][N + 5], d[N + 5], r[N + 5];
bool v[P + 5];

/*
LL exp(LL a, LL b, LL mod) {
    LL res = 1;
    while (b) {
        if (b & 1) (res *= a) %= mod;
        (a *= a) %= mod, b >>= 1;
    }
    return res;
}
*/

LL ex_gcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int res = ex_gcd(b, a % b, y, x);
    y -= x*(a/b);
    return res;
}

LL gcd(LL a, LL b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

LL lcm(LL a, LL b) {
    return a/gcd(a, b)*b;
}

LL inv(LL a, LL mod) {
    LL x, y;
    LL t = ex_gcd(a, mod, x, y);
    if (t != 1) return -1;
    return (x % mod + mod ) % mod;
}

LL gauss(int n, int m, LL mod) {
    int flag = 0;
    LL res = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) b[i][j] = a[i][j];
    for (int k = 0; k < n; ++k) {
        int max_k = k;
        for (int i = k + 1; i < n; ++i)
            if (b[i][k] > b[max_k][k]) max_k = i;
        if (max_k != k) {
            for (int j = k; j < m; ++j) swap(b[k][j], b[max_k][j]);
            flag ^= 1;
        }
        LL t = inv(b[k][k], mod);
        for(int j = k + 1; j < m; ++j) {  
            b[k][j] *= t;
            b[k][j] %= mod;
            if (b[k][j] < 0) b[k][j] += mod;
            for (int i = k + 1; i < n; ++i) {
                b[i][j] -= (b[i][k]*b[k][j] % mod);
                b[i][j] %= mod;
                if (b[i][j] < 0) b[i][j] += mod;
            }  
        }  
        res *= b[k][k];
        res %= mod;
        if (res < 0) res += mod;
    }
    if (flag) res *= -1;
    if (res < 0) res += mod;
    return res;
}

int deal(int l, int r, LL m) {
    int res = 0;
    for (int i = l + 1; i < r && m != 1; ++i)
        while (m % i == 0) d[res++] = i, m /= i;
    return res;
}

LL china_remain(int n, LL mod) {
    LL a = d[0], c1 = r[0] == 0 ? d[0] : r[0];
    for (int i = 1; i < n; ++i) {
        LL b = d[i], c2 = r[i], x, y;
        LL dd = ex_gcd(a, b, x, y);
        LL c = c2 - c1, b1 = b/dd;
        x = ((c/dd*x) % b1 + b1) % b1;
        c1 += a*x, a *= b1;
    }
    return c1 % mod;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) scanf("%I64d", &a[i][j]);
        if (m == 1) {
            printf("0\n");
            continue;
        }
        int len = deal(1000, P, (LL)m);
        for (int i = 0; i < len; ++i) r[i] = gauss(n, n, d[i]);
        printf("%I64d\n", china_remain(len, (LL)m));
    }
    return 0;
}

转载保留版权:http://haipz.com/blog/i/5572 - 海胖博客