結果

問題 No.2324 Two Countries within UEC
コンテスト
ユーザー rurun
提出日時 2023-05-28 15:45:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 744 bytes
コンパイル時間 1,929 ms
コンパイル使用メモリ 193,440 KB
最終ジャッジ日時 2025-02-13 13:55:03
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 返り値: 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;
}

int main() {
  lint n, m, p, q;
  cin >> n >> m >> p >> q;
  for (int i = 0; i < q; i++) {
    lint x, f;
    cin >> x >> f;
    lint s, t;
    extGCD(x, p, s, t);
    s *= f/gcd(x, p), t *= f/gcd(x, p);
    lint mi = max((s/p)*p, 0LL);
    lint ma = min((m/p)*p, m);
    if (f == 0) cout << m/p << endl;
    else cout << (ma-mi+p)/p << endl;

  }
}
0