結果

問題 No.187 中華風 (Hard)
ユーザー ミドリムシミドリムシ
提出日時 2022-04-05 21:27:02
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 197 ms / 3,000 ms
コード長 4,361 bytes
コンパイル時間 1,739 ms
コンパイル使用メモリ 177,544 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 05:39:17
合計ジャッジ時間 5,364 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 162 ms
5,248 KB
testcase_03 AC 146 ms
5,248 KB
testcase_04 AC 189 ms
5,248 KB
testcase_05 AC 186 ms
5,248 KB
testcase_06 AC 197 ms
5,248 KB
testcase_07 AC 196 ms
5,248 KB
testcase_08 AC 141 ms
5,248 KB
testcase_09 AC 134 ms
5,248 KB
testcase_10 AC 133 ms
5,248 KB
testcase_11 AC 187 ms
5,248 KB
testcase_12 AC 191 ms
5,248 KB
testcase_13 AC 57 ms
5,248 KB
testcase_14 AC 58 ms
5,248 KB
testcase_15 AC 146 ms
5,248 KB
testcase_16 AC 147 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 1 ms
5,248 KB
testcase_20 AC 149 ms
5,248 KB
testcase_21 AC 2 ms
5,248 KB
testcase_22 AC 197 ms
5,248 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'std::tuple<long long int, long long int, long long int> extgcd(lint, lint)':
main.cpp:38:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   38 |     auto [x, y, g] = extgcd(b, a % b);
      |          ^
main.cpp: In function 'lint modinv(lint, lint)':
main.cpp:47:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   47 |     auto [x, y, g] = extgcd(a, modulo);
      |          ^
main.cpp: In function 'std::pair<long long int, long long int> CRT(lint, lint, lint, lint)':
main.cpp:55:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   55 |     auto [b, c, g] = extgcd(m1, m2);
      |          ^
main.cpp: In function 'int main()':
main.cpp:134:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  134 |     auto [x, l] = Garner(a, m, 1000000007);
      |          ^

ソースコード

diff # 

//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
constexpr lint mod = 1e9 + 7;
#define all(x) begin(x), end(x)
#define bitcount(n) __builtin_popcountll((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzll(x))
#define rep(i, n) for(int i = 0; i < int(n); i++)
#define rep2(i, l, r) for(int i = int(l); i < int(r); i++)
#define repr(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define repr2(i, l, r) for(int i = int(r) - 1; i >= int(l); i--)
#define accumulate you cannot use this word!
constexpr int inf9 = 1e9; constexpr lint inf18 = 1e18;
inline void Yes(bool condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class itr> void array_output(itr start, itr goal){ for(auto i = start; i != goal; i++) cout << (i == start ? "" : " ") << (*i); cout << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(b) return gcd(b, a % b); else return a; }
template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
template<class T> bool chmax(T &a, const T &b){ if(a < b){ a = b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b < a){ a = b; return 1; } return 0; }
inline int has(lint i, int j){ return (i >> j) & 1; }
int dy[4] = {1, 0, -1, 0}; int dx[4] = {0, 1, 0, -1};
bool is_inside(lint y, lint x, lint H, lint W){ return (0 <= y && y < H && 0 <= x && x < W); }

struct io_init {
    io_init() {
        cin.tie(nullptr); cout.tie(nullptr);
        std::ios::sync_with_stdio(false);
    }
} io_init;

tuple<lint, lint, lint> extgcd(lint a, lint b){ // Need: a, b >= 0
    if(b == 0){
        return {1, 0, a};
    }
    auto [x, y, g] = extgcd(b, a % b);
    return {y, x - (a / b) * y, g};
}

lint signed_mod(lint x, lint modulo) {
    return (x % modulo + modulo) % modulo;
}

lint modinv(lint a, lint modulo){ // Need: gcd(x, modulo) = 1
    auto [x, y, g] = extgcd(a, modulo);
    return signed_mod(x, modulo);
}

pair<lint, lint> CRT(lint a1, lint m1, lint a2, lint m2){ // return (a, m)
    a1 = signed_mod(a1, m1);
    a2 = signed_mod(a2, m2);
    
    auto [b, c, g] = extgcd(m1, m2);
    if(a1 % g != a2 % g) return {-1, -1};
    
    lint m = m1 / g * m2;
    lint tmp = ((a2 - a1) / g) * b % (m2 / g);
    lint a = tmp * m1 + a1;
    a = signed_mod(a, m);
    return {a, m};
}

pair<lint, lint> Garner_simple(vector<lint> a, vector<lint> m, lint MOD = LONG_LONG_MAX){ // Need: m はそれぞれが互いに素 / return (a, m)
    int n = int(a.size());
    rep(i, n) a[i] = signed_mod(a[i], m[i]);
    
    m.push_back(MOD);
    
    lint coefs[n + 1], val_sums[n + 1];
    rep(i, n + 1) coefs[i] = 1;
    rep(i, n + 1) val_sums[i] = 0;
    rep(i, n){
        lint t = a[i] - val_sums[i];
        t = signed_mod(t, m[i]);
        t = t * modinv(coefs[i], m[i]) % m[i];
//        cout << t << endl;
        
        rep2(j, i + 1, n + 1){
            (val_sums[j] += t * coefs[j]) %= m[j];
            (coefs[j] *= m[i]) %= m[j];
        }
    }
    
//    rep(i, n + 1) cout << val_sums[i] << " " << coefs[i] << endl;
    
    return {val_sums[n], coefs[n]};
}

pair<lint, lint> Garner(vector<lint> a, vector<lint> m, lint MOD = LONG_LONG_MAX){ // return (a, m)
    int n = int(a.size());
    rep(i, n) rep(j, i){
        lint g = gcd(m[i], m[j]);
        if(a[i] % g != a[j] % g) return {-1, -1};
        
        m[i] /= g;
        m[j] /= g;
        lint gi = gcd(m[i], g), gj = g / gi;
        while(true){
            lint move = gcd(gi, gj);
            if(move == 1) break;
            
            gj /= move;
            gi *= move;
        }
        
        m[i] *= gi;
        m[j] *= gj;
        
        a[i] %= m[i], a[j] %= m[j];
    }
    
//    rep(i, n) cout << a[i] << " " << m[i] << endl;
//    cout << endl;
    return Garner_simple(a, m, MOD);
}


int main(){
    int n;
    cin >> n;
    vector<lint> a(n), m(n);
    bool is_zero = true;
    rep(i, n){
        lint x, y;
        cin >> x >> y;
        a[i] = x;
        m[i] = y;
        
        if(x > 0) is_zero = false;
    }
    
    auto [x, l] = Garner(a, m, 1000000007);
    if(x == -1){
        cout << -1 << endl;
    }else if(is_zero){
        cout << l << endl;
    }else{
        cout << x << endl;
    }
}
0