牛客网-对称与反对称 【逆元】

链接：https://www.nowcoder.com/acm/contest/94/H
来源：牛客网

给出一个N*N的方阵A。构造方阵B,C:
使得A = B + C.其中 B为对称矩阵，C为反对称矩阵。
对于方阵S中的任意元素,若(S)ij = (S)ji,则称S为对称矩阵
对于方阵T中的任意元素,若(T)ij = -(T)ji,则称T为反对称矩阵
注意，所有运算在模M意义下

输入描述:

输入包含多组数据，处理到文件结束
每组数据，第一行包含两个正整数N,M(1 <= N <= 1000, 1 <= M <= 1000,000,001)分别表示方阵大小与模数，其中M必定为奇数。
接下来的N行，每行有N个非负整数，表示方阵A(0<=A

_ij

<=1000,000,000)。

输出描述:

对于每组数据，将反对称矩阵$C$在$N$行中输出；
若不存在解，则输出"Impossible"；
若存在多解，则输出任意解。
(注意最后的输出全为非负数）

示例1

输入

2 19260817
0 1
1 0

输出

0 0
0 0


公式很好推 c[i][j] = (a[i][j] - a[j][i]) / 2;
主要是除以二的时候会除不整，所以要用逆元。
可以说是一道逆元的模板题了。

附ac代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
const int maxn = 1111;
ll a[maxn][maxn], c[maxn][maxn];
ll exgcd(ll a, ll b, ll& x, ll &y) {
    ll d = a;
    if(b != 0) {
        d = exgcd(b, a % b, y, x);
        y -= (a / b) * x;
        
    } else {
        x = 1; y = 0;
    }
    return d;
}
ll getm(ll a, ll m) {
    ll x, y;
    exgcd(a, m, x, y);
    return (m + x % m) % m;
}
int main() {
    int n;
    ll m;
    while(~scanf("%d %lld", &n, &m)) {
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                scanf("%lld", &a[i][j]);
            }
        }
        ll mm = getm(ll(2), m);
    //    printf("%lld mmm
",mm);
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                c[i][j] = ((a[i][j] - a[j][i]) * mm) % m;
                if(c[i][j] < 0) c[i][j] += m;
            }
        }
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= n; ++j) {
                if(j == 1) printf("%lld", c[i][j]);
                else printf(" %lld", c[i][j]);
            }
            printf("
");
        }
    }
    return 0;
}