Test/yukicoder/ChineseRemainderTheorem.test.cpp

View this file on GitHub
Last update: 2021-07-06 14:36:38+09:00
Problem: https://yukicoder.me/problems/447

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/447"

#include<bits/stdc++.h>
using namespace std;

#include"../../Other/Template.cpp"
#include"../../Mathematics/ChineseRemainderTheorem.cpp"

int main() {
    long long X1,Y1,X2,Y2,X3,Y3;
    cin >> X1 >> Y1 >> X2 >> Y2 >> X3 >> Y3;
    pair<long long,long long> ret = CRT({X1,X2,X3},{Y1,Y2,Y3});
    if(ret.second == -1) cout << -1 << endl;
    else {
        if(ret.first == 0) cout << ret.second << endl;
        else cout << ret.first << endl;
    }
}

#line 1 "Test/yukicoder/ChineseRemainderTheorem.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/447"

#include<bits/stdc++.h>
using namespace std;

#line 1 "Other/Template.cpp"
constexpr int Inf = 2000000030;
constexpr long long INF= 2000000000000000000;

template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
#line 1 "Mathematics/ChineseRemainderTheorem.cpp"
//extgcd(a,b,x,y):ax+by=gcd(a,b)を満たす(x,y)が格納される　返り値はgcd(a,b)
long long extgcd(long long a,long long b,long long &x,long long &y) {
    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extgcd(b,a % b,y,x);
    y -= a / b * x;
    return d;
}

//CRT(b,m):n次合同方程式を解く。答えは x = R (mod M)の形で表される（解が無い場合は(0,-1)の形で表される）
pair<long long,long long> CRT(vector<long long> r,vector<long long> m) {
    if(r.empty() || m.empty()) return {0,1};
    long long R = r.front();
    long long M = m.front();
    for(int i = 1;i < (int)r.size();i++) {
        long long x,y;
        long long d = extgcd(M,m.at(i),x,y);
        if((r.at(i) - R) % d != 0) return {0,-1};
        long long tmp = (r.at(i) - R) / d % (m.at(i) / d) * x % (m.at(i) / d);
        R += M * tmp;
        M *= m.at(i) / d;
    }
    R %= M;
    if(R < 0) R += M;
    return {R,M};
}
#line 8 "Test/yukicoder/ChineseRemainderTheorem.test.cpp"

int main() {
    long long X1,Y1,X2,Y2,X3,Y3;
    cin >> X1 >> Y1 >> X2 >> Y2 >> X3 >> Y3;
    pair<long long,long long> ret = CRT({X1,X2,X3},{Y1,Y2,Y3});
    if(ret.second == -1) cout << -1 << endl;
    else {
        if(ret.first == 0) cout << ret.second << endl;
        else cout << ret.first << endl;
    }
}