結果

問題 No.3179 3 time mod
ユーザー Thread
提出日時 2025-06-13 21:49:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,526 bytes
コンパイル時間 1,517 ms
コンパイル使用メモリ 195,376 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-14 01:40:57
合計ジャッジ時間 2,638 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long ;

long long exGcd(long long a,long long b , long long &x,long long &y){
if(b==0){
    x=1,y=0;
    return a;
}
long long x1,y1;
long long d= exGcd(b,a%b,x1,y1);
x = y1;
y = x1 - (a/b)*y1;
return d;
}


pair<ll, ll> combine_congruence(ll a1, ll m1, ll a2, ll m2) {
    ll x, y;
    ll g = exGcd(m1, m2, x, y);
    ll diff = a2 - a1;

    if (diff % g != 0) {
        return {-1, -1};
    }
    ll lcm = m1 / g * m2; 
    ll step = (diff / g * x) % (m2 / g);
    ll result = (a1 + step * m1) % lcm;

    if (result < 0) result += lcm;
    return {result, lcm};
}

ll solver(ll N, ll A, ll P, ll B, ll Q, ll C, ll R) {
    auto [x1,l1] = combine_congruence(A, P, B, Q);
    if (x1== -1) return 0; 
    auto [x0,lcm]= combine_congruence(x1,l1,C,R);
    if (x0== -1)return 0; 
    if (x0> N)return 0;
    return (N -x0)/lcm+1;
}


void solve() {
    long long n ;
    cin>>n;
    long long p,q,r;
    cin>>p>>q>>r;
    long long a,b,c;
    cin>>a>>b>>c;
     // x%p == a
     // x%q == b
     // x%r == c

     // get the lcm of all 3 and the first solution then just do (n-f)/lcm;
     cout<<solver(n,a,p,b,q,c,r);

}



int main(){
    // initCombi();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.flush();
    cout<<fixed<<setprecision(9);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif  
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
0