#933826 (C++23) No.2558 中国剰余定理

• 問題: No.2558 中国剰余定理
• ユーザー: NATTO
• 提出日時: 2023-12-02 14:40:08
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 95 ms / 2,000 ms
• コード長: 2,424 bytes
• コンパイル時間: 5,183 ms
• コンパイル使用メモリ: 307,168 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-26 17:05:40
• 合計ジャッジ時間: 6,623 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	25 ms; 5,376 KB
testcase_03	AC	95 ms; 5,376 KB
testcase_04	AC	95 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	22 ms; 5,376 KB
testcase_09	AC	3 ms; 5,376 KB
testcase_10	AC	10 ms; 5,376 KB
testcase_11	AC	15 ms; 5,376 KB
testcase_12	AC	5 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	5 ms; 5,376 KB
testcase_16	AC	26 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	29 ms; 5,376 KB
testcase_19	AC	39 ms; 5,376 KB
testcase_20	AC	8 ms; 5,376 KB
testcase_21	AC	19 ms; 5,376 KB
testcase_22	AC	2 ms; 5,376 KB
testcase_23	AC	3 ms; 5,376 KB
testcase_24	AC	29 ms; 5,376 KB
testcase_25	AC	30 ms; 5,376 KB
testcase_26	AC	4 ms; 5,376 KB
testcase_27	AC	3 ms; 5,376 KB
testcase_28	AC	20 ms; 5,376 KB
testcase_29	AC	2 ms; 5,376 KB
testcase_30	AC	10 ms; 5,376 KB
testcase_31	AC	5 ms; 5,376 KB

ソースコード

#pragma region header
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

// clang-format off

struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;

inline void IN(void)
{
    return;
}

template <typename First, typename... Rest>
void IN(First &first, Rest &...rest)
{
    cin >> first;
    IN(rest...);
    return;
}
template <typename T>
istream &operator>>(istream &is, pair<T, T> &p)
{
    is >> p.first >> p.second;
    return is;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
    for (auto &x : v)
        is >> x;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    for (auto &x : v)
        os << x << " ";
    os << endl;
    return os;
}

// templetes
//alias
 
using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
using pll = pair<ll, ll>;
 
//define short
#define vec vector
#define all(obs) (obs).begin(), (obs).end()
#define YESNO(cond) (cond) ? cout << "YES" << endl : cout << "NO" << endl;
#define YesNo(cond) (cond) ? cout << "Yes" << endl : cout << "No" << endl;
#define yesno(cond) (cond) ? cout << "yes" << endl : cout << "no" << endl;
#define sortv(obs) sort(all(obs))
#define rsortv(obs) reverse(sort(all(obs)))
#define bitu(n,i) (((n)>>(i))&1)
#define dig10(n) to_string(n).size()
#define bcnt(n) __builtin_popcount(n)
#define bcntll(n) __builtin_popcountll(n)
#define F first
#define S second
#define pb push_back
#define pq priority_queue


//define loop
#define rep(i, a,b) for(ll i = a; i < (b); i++)
#define rrep(i, a,b) for(ll i = a; i >= (b); i--)
//define INF
const ll INF = 1e18;

template <typename T1,typename T2>
inline void chmin(T1 &a,T2 b){
    if(a>b) a = b;
}
template <typename T1,typename T2>
inline void chmax(T1 &a,T2 b){
    if(a<b) a = b;
}


#pragma endregion header

// clang-format on

ll inv(ll a, ll m){
    ll b = m, u = 1, v = 0;
    while(b){
        ll t = a/b;
        a -= t*b; swap(a,b);
        u -= t*v; swap(u,v);
    }
    u %= m;
    if(u<0) u += m;
    return u;
}

int main(){
    ll A,B,a,b;
    cin>>A>>B>>a>>b;
    rep(i,1, A*B){
        if((i%A==a)&&(i%B==b)){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<0<<endl;

}