結果

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

ソースコード

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<i64, i64>;
using el = tuple<i64, i64, i64>;
using mint = atcoder::modint998244353;

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

i64 pow(i64 x, i64 n, i64 m) {
  i64 res = 1;
  i64 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) が格納される
i64 extGCD(i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    i64 d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

void _main() {
  i64 n, p, q, r, a, b, c;
  cin >> n >> p >> q >> r >> a >> b >> c;
  i64 x = p, y = a;
  {
    i64 s, t;
    i64 g = extGCD(x, q, s, t);
    assert(g == 1);
    i64 C = b - y;
    s *= C, t *= C;
    assert(x * s + q * t == b - y);
    assert(x * s + y == q * (-t) + b);
    i64 V = x * s + y;
    x = x * q, y = V;
    y = (y % x + x) % x;
  }
  assert(y % p == a);
  assert(y % q == b);
  {
    i64 s, t;
    i64 g = extGCD(x, r, s, t);
    assert(g == 1);
    i64 C = c - y;
    s *= C, t *= C;
    assert(x * s + r * t == c - y);
    assert(x * s + y == r * (-t) + c);
    i64 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);
  i64 ans = (n - y) / x + 1;
  cout << ans << "\n";
}
0