結果

問題 No.2324 Two Countries within UEC
コンテスト
ユーザー Peach2587
提出日時 2023-05-28 15:07:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,316 bytes
コンパイル時間 1,619 ms
コンパイル使用メモリ 170,824 KB
実行使用メモリ 1,257,540 KB
最終ジャッジ日時 2024-12-27 04:49:11
合計ジャッジ時間 56,323 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 4 TLE * 10 MLE * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359879323846264338327950288419;
const int INF = 2147483647;
using p = pair<int, int>;

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) { u += m; }
    return u;
}

int main() {
    ll n, m, p, q;
    cin >> n >> m >> p >> q;
    vector<int> tori(p + 1);
    for (int i = 1; i <= m; i++) { tori[i % p]++; }
    for (int i = 0; i < tori.size(); i++) { cerr << i << " " << tori[i] << endl; }
    for (int i = 0; i < q; i++) {
        ll ans = 0;
        int x, f;
        cin >> x >> f;
        x %= p;
        ll inv = 0;
        if (f != 0) {
            inv = modinv(x, p) * f % p;
            //cerr << "inv = " << inv << endl;
            for (int i = 1; i * inv <= p; i++) {
                //cout << i*inv << " : " << tori[i * inv] << endl;
                ans += tori[i * inv];
            }
        } else {
            if (x % p == 0) { ans += tori[1]; }
            for (int i = 2; i * p <= m; i++) { ans += tori[inv * i * p]; }
        }
        cout << tori[inv] << endl;
    }

    return 0;
}
0