CF509D Restoring Numbers 题解

题目描述

给你一个 $n \times m$ 的矩阵 $v$。

$v_{i, j} = (a_i + b_j) \bmod{k}$。

求两个序列及其模数 $k$。

思路

注意到，如果我们将 $a$ 序列中的所有数加上一，$b$ 序列中的所有数减去一，整个矩阵不会改变。

因此我们不妨设 $a1 = 0$，通过第一列推出 $b$ 序列的值，进而推出 $a$ 序列的值。现在我们为每个格子 $(i, j)$ 计算一个误差 $error = a_i + b_j - v{i, j}$。

如果所有的误差均为 $0$，则已经找到了一个满足条件的矩阵。否则意味着误差一定是 $k$ 的倍数，即 $k$ 一定是所有误差的公因数。另外 $k$ 还必须大于所有 $v$ 矩阵中出现的数。如果满足这两个条件则有解，否则无解。

代码

/**
 * @file CF509D.cpp
 * @author distjr_
 * @brief Solution of CF509D
 */
#include <cstdio>
#include <cstdlib>
#define MAXN 105
#define int long long
// #define DEBUG
using namespace std;

int n, m, v[MAXN][MAXN], a[MAXN], b[MAXN], error, k = 0;
bool flag = true;
int (*gcd)(int, int) = [](int a, int b)
{ return ((b == 0) ? a : gcd(b, a % b)); };


signed main()
{
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%lld", &v[i][j]);
    for (int i = 1; i <= m; ++i)
        b[i] = v[1][i];
    for (int i = 1; i <= n; ++i)
        a[i] = v[i][1] - b[1];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            error = abs(a[i] + b[j] - v[i][j]), k = gcd(k, error);
    if (!k)  // k为0，故最后所有的误差值都是0，直接给k赋值为1e9+7即可
        k = 1000000007;
    for (int i = 1; i <= n && flag; ++i)
        for (int j = 1; j <= m; ++j)
            if (v[i][j] >= k)
            {
                flag = false;
                break;
            }
    if (!flag)
    {
        printf("NO\n");
        return 0;
    }
    printf("YES\n%lld\n", k);
    for (int i = 1; i <= n; ++i)
        printf("%lld ", (a[i] + k) % k);
    printf("\n");
    for (int i = 1; i <= m; ++i)
        printf("%lld ", (b[i] + k) % k);
    printf("\n");
    return 0;
}

以上。如有问题烦请指出，谢谢。