結果

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

ソースコード

diff # 

#include <iostream>
using namespace std;
using ll = long long;

ll extgcd(ll a, ll b, ll& x, ll& y){
  if(b==0){
    x = 1; y = 0;
    return a;
  }
  ll x1, y1;
  ll g = extgcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return g;
}

int main(){
  ll n, p, q, r, a, b, c;
  cin >> n >> p >> q >> r >> a >> b >> c;

  ll pq = p * q;
  ll pqr = pq * r;

  // -- ① p,q を結合して s を作る --
  ll x, y;
  extgcd(p, q, x, y);
  // x ≡ p^{-1} mod q,  y ≡ q^{-1} mod p
  x = (x % q + q) % q;
  y = (y % p + p) % p;

  // s ≡ a (mod p),  s ≡ b (mod q)
  __int128 t1 = (__int128)a * q % pq * y % pq;
  __int128 t2 = (__int128)b * p % pq * x % pq;
  ll s = (ll)((t1 + t2) % pq);

  // -- ② s,r を結合して t を作る --
  extgcd(pq, r, x, y);
  // x ≡ (pq)^{-1} mod r,  y ≡ r^{-1} mod pq
  x = (x % r + r) % r;
  y = (y % pq + pq) % pq;

  // CRT の公式 t = ( pq*c * x + s*r * y ) mod (pqr)
  __int128 u1 = (__int128)pq * c % pqr * x % pqr;
  __int128 u2 = (__int128)s * r % pqr * y % pqr;
  ll t = (ll)((u1 + u2) % pqr);

  // -- ③ 解の個数を一発で出す --
  if(t > n){
    cout << 0 << "\n";
  } else {
    // k = 0 .. floor((n-t)/pqr)
    ll kmax = (n - t) / pqr;
    cout << (kmax + 1) << "\n";
  }
  return 0;
}
0