結果

問題 No.1175 Simultaneous Equations
ユーザー soraie_soraie_
提出日時 2020-09-30 20:12:27
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 9,100 bytes
コンパイル時間 2,129 ms
コンパイル使用メモリ 189,316 KB
実行使用メモリ 4,500 KB
最終ジャッジ日時 2023-09-20 14:56:51
合計ジャッジ時間 2,805 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,500 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#include<outputchecker.cpp>
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
/*----------------------------------ここからマクロ----------------------------------*/
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define vecin(a) rep(i,a.size())cin >> a[i]
#define overload4(_1,_2,_3,_4,name,...) name
/*#define rep1(n) for(int i=0;i<(int)n;++i)
#define rep2(i,n) for(int i=0;i<(int)n;++i)
#define rep3(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define rep4(i,a,b,c) for(int i=(int)a;i<(int)b;i+=(int)c)*/
#define rep1(n) for(ll i=0;i<(ll)n;++i)
#define rep2(i,n) for(ll i=0;i<(ll)n;++i)
#define rep3(i,a,b) for(ll i=(ll)a;i<(ll)b;++i)
#define rep4(i,a,b,c) for(int i=(ll)a;i<(ll)b;i+=(ll)c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#ifdef _DEBUG
#define debug1(a) cerr << #a << ": " << a << "\n"
#define debug2(a,b) cerr << #a << ": " << a << ", " << #b << ": " << b << "\n"
#define debug3(a,b,c) cerr << #a << ": " << a << ", " << #b << ": " << b << ", " << #c << ": " << c << "\n"
#define debug4(a,b,c,d) cerr << #a << ": " << a << ", " << #b << ": " << b << ", " << #c << ": " << c << ", " << #d << ": " << d << "\n"
#define debug(...) overload4(__VA_ARGS__,debug4,debug3,debug2,debug1)(__VA_ARGS__)
#define vecout(a) cerr << #a << ": [";rep(i,a.size()){cerr << a[i];cerr << (i == a.size() - 1 ? "":",");}cerr << "]\n"
#else
#define debug(...)
#define vecout(a)
#endif
#define mp make_pair
//struct doset{doset(int n){cout << fixed << setprecision(n);cerr << fixed << setprecision(n);}};
//struct myset{myset(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}};
void myset(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
void doset(int n){cout << fixed << setprecision(n);}
using ll = long long;
using ld = long double;
using dou = double;
const int inf = 1 << 30;
const ll INF = 1LL << 60;
const ld pi = 3.14159265358;
const ll mod1 = 1000000007LL;
const ll mod2 = 998244353LL;
typedef pair<ll,ll> P;
template<class T, class U> inline bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> inline bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
//nのm乗をMODで割ったあまりO(logm)
ll modpow(ll n,ll m,ll MOD){
    if(m == 0)return 1;
    if(m < 0)return 0;
    ll res = 1;
    n %= MOD;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

ll mypow(ll n,ll m){
    if(m == 0)return 1;
    if(m < 0)return -1;
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n);
        m >>= 1;
        n *= n;
    }
    return res;
}

//素数判定O(sqrt(N))
template<class T>
inline bool isp(T n){
    bool res = true;
    if(n == 1 || n == 0)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}


inline bool Yes(bool b = 1){cout << (b ? "Yes\n":"No\n");return b;}
inline bool YES(bool b = 1){cout << (b ? "YES\n":"NO\n");return b;}


map<ll,ll> primefactor(ll n){
    map<ll,ll> ma;
    if(n <= 1)return ma;
    ll m = n;
    for(ll i = 2;i * i <= n;i++){
        while(m % i == 0){
            ma[i]++;
            m /= i;
        }
    }
    if(m != 1)ma[m]++;
    return ma;
}

ll __lcm(ll a,ll b){
    return a / __gcd(a,b) * b;
}


template<ll MOD = mod1>
struct fac_solver{
private:
    ll cmax;
    vector<ll> fac,finv,inv;
public:
    fac_solver(ll n = 100000):cmax(n),fac(n),finv(n),inv(n){
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (ll i = 2; i < cmax; i++){
            fac[i] = fac[i - 1] * i % MOD;
            inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
            finv[i] = finv[i - 1] * inv[i] % MOD;
        }
    }

    //二項係数計算nCk
    ll nCk(ll n, ll k){
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
    }

    ll nPk(ll n,ll k){
        if(n < k || n < 0 || k < 0)return 0;
        return fac[n] * finv[n - k] % MOD;
    }

    ll stair_pow(ll n){return fac[n];}
};



/*----------------------------------マクロここまで----------------------------------*/

struct rat{
    ll ue,si;
    int sign;
    rat(ll ue_ = 0,ll si_ = 1){
        ll G = __gcd(ue_,si_);
        ue_ /= G;si_ /= G;
        sign = 1;
        if(ue_ < 0 || si_ < 0)sign = -1;
        ue = abs(ue_);si = abs(si_);
    }
    rat operator-()const{
        rat res(*this);
        res.sign *= -1;
        return res;
    }
    rat ABS()const{
        rat res(*this);
        res.sign = 1;
        return res;
    }
    void operator=(const rat& x){
        ue = x.ue;si = x.si;sign = x.sign;
    }
    rat &operator+=(const rat& x){
        if(sign != x.sign){
            *this -= (-x);
            return *this;
        }
        ll G = __gcd(si,x.si);
        ue = ue * (x.si / G) + x.ue * (si / G);
        ll G1 = __gcd(si,ue);
        si /= G1;ue /= G1;
        ll G2 = __gcd(x.si,ue);
        ue /= G2;
        si = x.si / G2 * si * G;
        return *this;
    }
    rat &operator-=(const rat& x){
        if(sign != x.sign){
            *this += (-x);
            return *this;
        }
        ll G = __gcd(si,x.si);
        ue = ue * (x.si / G) - x.ue * (si / G);
        if(ue < 0){
            sign *= -1;
            ue = -ue;
        }
        ll G1 = __gcd(si,ue);
        si /= G1;ue /= G1;
        ll G2 = __gcd(x.si,ue);
        ue /= G2;
        si = x.si / G2 * si * G;
        return *this;
    }
    rat operator+(const rat& x)const{
        return rat(*this) += x;
    }
    rat operator-(const rat& x)const{
        return rat(*this) -= x;
    }
    rat &operator*=(const rat& x){
        sign *= x.sign;
        ll G1 = __gcd(ue,x.si),G2 = __gcd(si,x.ue);
        rat X = x;
        ue /= G1;X.si /= G1;si /= G2;X.ue /= G2;
        ue *= X.ue;si *= X.si;
        return *this;
    }
    rat operator*(const rat& x)const{
        return rat(*this) *= x;
    }
    rat inv()const{
        rat res(*this);
        swap(res.ue,res.si);
        return res;
    }
    rat operator/(const rat& x)const{
        return rat(*this) *= x.inv();
    }
    void operator/=(const rat& x){
        *this = *this / x;
    }
    bool operator==(const rat& x)const{return ue == x.ue && si == x.si && sign == x.sign;}
    bool operator!=(const rat& x)const{return !(rat(*this) == x);}
    bool operator<(const rat& x)const{
        if(sign != x.sign)return sign < x.sign;
        if(sign == -1){
            ll G = __gcd(si,x.si);
            return ue * (x.si / G) > x.ue * (si / G);
        }
        else{
            ll G = __gcd(si,x.si);
            return ue * (x.si / G) < x.ue * (si / G);
        }
    }
    bool operator<=(const rat& x)const{
        return rat(*this) == x || rat(*this) < x;
    }
    bool operator>(const rat& x)const{
        return !(rat(*this) <= x);
    }
    bool operator>=(const rat& x)const{
        return !(rat(*this) < x);
    }
    ll modexpr(const ll M){
        return ue % M * modpow(si,M - 2,M) % M;
    }
    ld approximation(){
        return (ld)(ue) / (ld)(si) * sign;
    }
    friend istream& operator>>(istream& is,rat& x){
        ll u,s;
        is >> u >> s;
        rat res(u,s);
        x = res;
        return is;
    }
    friend ostream& operator<<(ostream& os,const rat& x){
        if(x.sign == -1)os << "-";
        os << x.ue << " / " << x.si;
        return os;
    }
};


vector<rat>simultaneous_equations(vector<vector<rat>> &kei,vector<rat> &cns){
    int sz = kei.size();
    if(sz == 1){
        return {cns[0] / kei[0][0]};
    }
    vector<vector<rat>> nextk(sz - 1,vector<rat>(sz - 1));
    vector<rat> nextc(sz - 1);
    rep(i,sz - 1){//上を下に合わせる
        if(kei[i][0] == 0){
            rep(j,sz - 1){
                nextk[i][j] =  kei[i][j + 1];
            }
            nextc[i] = cns[i];
        }
        else{
            rat ret = kei[i + 1][0] / kei[i][0];
            rep(j,sz - 1){
                nextk[i][j] = kei[i][j + 1] * ret - kei[i + 1][j + 1];
            }
            nextc[i] = cns[i] * ret - cns[i + 1];
        }
    }
    auto na = simultaneous_equations(nextk,nextc);
    rat finalcns = cns[0];
    rep(i,1,sz){
        finalcns -= kei[0][i] * na[i - 1];
    }
    na.insert(na.begin(),finalcns / kei[0][0]);
    return na;
}

int main(){
    myset();
    ll a,b,c,d,e,f;
    cin >> a >> b >> c >> d >> e >> f;
    vector<vector<rat>> test(2,vector<rat>(2));
    vector<rat> cns(2);
    cns[0] = rat(c);cns[1] = rat(f);
    test[0][0] = rat(a);test[0][1] = rat(b);test[1][0] = rat(d);test[1][1] = rat(e);
    auto ans = simultaneous_equations(test,cns);
    doset(10);
    cout << ans[0].approximation() << " " << ans[1].approximation() << "\n";
    //vector<vector<rat>> vec = {{2,1}};vector<rat> v2 = {{8,1}};
    //cout << simultaneous_equations(vec,v2)[0] << "\n";
}
0