2015年2月2日 星期一

2015/02/02 Codeforces 509D. Restoring Numbers

/*
    你會發現
    如果你有一組解
    你把 a 同+1 b同-1
    又會是ㄧ組解

    所以 a,b的值
    可以 藉由任意給定
    ㄧ個值 全部求出

    比較關鍵的就是
    如何決定 k了
    我們先 檢驗一個比較弱的條件
    (a+b)%k == w%k
    
    每當我們找到ㄧ組 a+b != w 時
    我們便知 k 必須是 abs(w-a-b)的因數
    不斷的做 最大公因數

    最後再用迴圈一遍
    檢查 (a+b)%k == w
*/
// http://codeforces.com/contest/509/problem/D
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;

ll N, M;
ll W[1000][1000];
ll a[1000], b[1000];

ll gcd(ll x, ll y)
{
    while( x && y )
    {
        if( x < y ) swap(x, y);
        x %= y;
    }

    return x+y;
}

int main()
{
    cin>>N>>M;

    for(ll Ni = 0; Ni < N; Ni++)
        for(ll Mi = 0; Mi < M; Mi++)
            cin>>W[Ni][Mi];

    bool OK = true;
    ll MOD = 0;

    a[0] = 0;

    for(ll Mi = 0; Mi < M; Mi++)
        b[Mi] = W[0][Mi];

    for(ll Ni = 1; Ni < N; Ni++)
    {
        a[Ni] = W[Ni][0]-b[0];

        for(ll Mi = 1; Mi < M; Mi++)
            if( a[Ni]+b[Mi] != W[Ni][Mi] )
            {
                ll d = abs(W[Ni][Mi]-a[Ni]-b[Mi]);
                MOD = gcd(MOD, d);
            }

    }

    if( !MOD ) MOD = 1e9+7;

    for(ll Ni = 0; Ni < N; Ni++)
        for(ll Mi = 0; Mi < M; Mi++)
        {
            a[Ni] = (a[Ni]+MOD)%MOD;
            b[Mi] = (b[Mi]+MOD)%MOD;

            if( (a[Ni]+b[Mi])%MOD != W[Ni][Mi] )
                OK = false;
        }

    if( OK )
    {
        puts("YES");

        cout<<MOD<<endl;

        for(ll Ni = 0; Ni < N; Ni++)
        {
            cout<<a[Ni];

            if( Ni+1 != N ) printf(" ");
            else puts("");
        }

        for(ll Mi = 0; Mi < M; Mi++)
        {
            cout<<b[Mi];

            if( Mi+1 != M ) printf(" ");
            else puts("");
        }
    }
    else
    {
        puts("NO");
    }
}

沒有留言:

張貼留言