test/aoj2659.test.cpp

Back to top page

• category: test
• View this file on GitHub
  • Last commit date: 2020-03-01 12:39:31+09:00
• see: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2659

Depends on

• math/CRT.cpp
• memo/macro.hpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2659"
#include "../memo/macro.hpp"
#include "../math/CRT.cpp"

signed main(void) {
    ll n, m, d;
    cin >> n >> m >> d;
    vector<ll> a(m);
    REP(i, m) cin >> a[i];
    REP(i, d) {
        vector<ll> x, y;
        REP(j, m) {
            ll r;
            cin >> r;
            if(r == -1) continue;
            x.push_back(r);
            y.push_back(a[j]);
        }

        vector<ll> v(x.size(), 1);
        PII p = crt(v, x, y);
        // p.second * k + p.first <= n である最大の整数
        if(p.first == -1 || n < p.first) {
            cout << -1 << endl;
            return 0;
        }
        ll k = (n-p.first) / p.second;
        n = p.second * k + p.first;
    }
    cout << n << endl;

    return 0;
}

#line 1 "test/aoj2659.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2659"
#line 1 "memo/macro.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
const ll INF = 1LL<<60;
#line 1 "math/CRT.cpp"
// BEGIN CUT
// ax + by = gcd(a, b) となる {x, y, gcd(a, b)} を返す
// O(log(min(a, b)))
ll extgcd(ll a, ll b, ll &x, ll &y) {
    ll g = a; x = 1, y = 0;
    if(b != 0) g = extgcd(b, a%b, y, x), y -= (a/b) * x;
    return g;
}

// a^-1 mod n を返す　存在しなければ-1
// O(log(n))
ll inv(ll a, ll n) {
    ll s, t;
    extgcd(a, n, s, t);
    return (n+s) % n;
}

// O(a.size*logM)
// 連立線形合同式 a[i] * x ≡ b[i] (mod m[i]) を解く
// オーバーフローには注意
pair<ll, ll> crt(const vector<ll>& a, const vector<ll>& b, const vector<ll>& m) {
    // (答えx, mod)
    pair<ll, ll> ret(0, 1);
    REP(i, a.size()) {
        ll s = a[i] * ret.second;
        ll t = b[i] - a[i] * ret.first;
        ll d = __gcd(m[i], s);
        if(t % d != 0) return make_pair(-1, -1);
        ll u = t / d * inv(s / d, m[i] / d) % (m[i] / d);
        ret.first += ret.second * u;
        ret.second *= m[i] / d;
        ret.first = (ret.first % ret.second + ret.second) % ret.second;
    }
    return ret;
}
// END CUT
#line 4 "test/aoj2659.test.cpp"

signed main(void) {
    ll n, m, d;
    cin >> n >> m >> d;
    vector<ll> a(m);
    REP(i, m) cin >> a[i];
    REP(i, d) {
        vector<ll> x, y;
        REP(j, m) {
            ll r;
            cin >> r;
            if(r == -1) continue;
            x.push_back(r);
            y.push_back(a[j]);
        }

        vector<ll> v(x.size(), 1);
        PII p = crt(v, x, y);
        // p.second * k + p.first <= n である最大の整数
        if(p.first == -1 || n < p.first) {
            cout << -1 << endl;
            return 0;
        }
        ll k = (n-p.first) / p.second;
        n = p.second * k + p.first;
    }
    cout << n << endl;

    return 0;
}

Back to top page