結果

問題 No.3179 3 time mod
ユーザー areik
提出日時 2025-06-13 21:42:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,578 bytes
コンパイル時間 4,194 ms
コンパイル使用メモリ 251,348 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-06-13 21:42:28
合計ジャッジ時間 5,276 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "atcoder/math.hpp"
#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) が格納される
long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long 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;
  }
  {
    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;
  i64 ans = (n - y) / x + 1;
  cout << ans << "\n";
}
0