結果

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

ソースコード

diff # 

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

using i32 = int;
using i64 = long long;
using f64 = long double;
using i128 = __int128_t;
using p2 = pair<i128, i128>;
using el = tuple<i128, i128, i128>;
using mint = atcoder::modint998244353;

void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}

i128 pow(i128 x, i128 n, i128 m) {
  i128 res = 1;
  i128 t = x % m;
  while (n > 0) {
    if (n & 1) {
      res = res * t % m;
    }
    t = t * t % m;
    n >>= 1;
  }
  return res;
}
//https://qiita.com/drken/items/b97ff231e43bce50199a
// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
i128 extGCD(i128 a, i128 b, i128 &x, i128 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    i128 d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

void _main() {
  i128 n, p, q, r, a, b, c;
  {
    i64 N, P, Q, R, A, B, C;
    cin >> N >> P >> Q >> R >> A >> B >> C;
    n = N, p = P, q = Q, r = R, a = A, b = B, c = C;
  }
  i128 x = p, y = a;
  {
    i128 s, t;
    i128 g = extGCD(x, q, s, t);
    assert(g == 1);
    i128 C = b - y;
    s *= C, t *= C;
    assert(x * s + q * t == b - y);
    assert(x * s + y == q * (-t) + b);
    i128 V = x * s + y;
    x = x * q, y = V;
    y = (y % x + x) % x;
  }
  assert(y % p == a);
  assert(y % q == b);
  {
    i128 s, t;
    i128 g = extGCD(x, r, s, t);
    assert(g == 1);
    i128 C = c - y;
    s *= C, t *= C;
    assert(x * s + r * t == c - y);
    assert(x * s + y == r * (-t) + c);
    i128 V = x * s + y;
    x = x * r, y = V;
    y = (y % x + x) % x;
  }
  if (n < y) {
    cout << "0\n";
    return;
  }
  assert(y % p == a);
  assert(y % q == b);
  assert(y % r == c);
  i128 ans = (n - y) / x + 1;
  cout << (i64)ans << "\n";
}
0