結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー HIR180
提出日時 2019-10-26 23:16:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 208 ms / 3,000 ms
コード長 2,121 bytes
コンパイル時間 1,812 ms
コンパイル使用メモリ 172,952 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 20:20:26
合計ジャッジ時間 5,442 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define SIZE 100005
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define pb push_back

template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; }
ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }

ll garner(vector<ll>b, vector<ll>m, ll mod){
    b.emplace_back(0);
    m.emplace_back(mod);

    vector<ll> coffs(b.size(), 1);
    vector<ll> constants(b.size(), 0);
    for(int i=0;i<b.size()-1;i++){
        ll v = (b[i] - constants[i]) * mod_inv<ll>(coffs[i], m[i]) % m[i];
        if (v < 0) v += m[i];

        for (int j = i + 1; j < b.size(); j++) {
            (constants[j] += coffs[j] * v) %= m[j];
            (coffs[j] *= m[i]) %= m[j];
        }
    }

    return constants[b.size() - 1];
}
ll gcd(ll a, ll b){
    if(a<b)swap(a,b);
    if(b==0) return a;
    else return gcd(b,a%b);
}
ll preGarner(vector <ll> &b, vector <ll> &m, ll MOD) {
    for (int i = 0; i < b.size(); i++) {
        for (int j = 0; j < i; j++) {
            ll g = gcd(m[i], m[j]);
            if ((b[i] - b[j]) % g != 0) return -1;

            m[i] /= g, m[j] /= g;
            ll gi = gcd(m[i], g), gj = g / gi;
            do {
                g = gcd(gi, gj);
                gi *= g, gj /= g;
            } while (g != 1);
            m[i] *= gi, m[j] *= gj;
            b[i] %= m[i], b[j] %= m[j];
        }
    }

    ll res = 1;
    for (int i = 0; i < b.size(); i++) (res *= m[i]) %= MOD;
    return res;
}

///////
vector<ll>B,M;
int n;
int main(){
	cin >> n;
	rep(i,n){ ll a,b; cin >> a >> b; B.pb(a); M.pb(b); }
	ll ret = preGarner(B,M,1000000007LL);
	rep(i,n) if(B[i] > 0) goto nxt;
	cout << ret << endl; return 0;
	nxt:;
	if(ret == -1) cout << "-1" << endl;
	else{
		cout << garner(B,M,1000000007LL) << endl;
	}
}
0