結果
問題 | No.2324 Two Countries within UEC |
ユーザー |
|
提出日時 | 2023-05-28 13:46:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 2,670 bytes |
コンパイル時間 | 1,817 ms |
コンパイル使用メモリ | 173,608 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-26 23:15:56 |
合計ジャッジ時間 | 4,911 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;constexpr long long safe_mod(long long x, long long m) {x %= m;if (x < 0) x += m;return x;}constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {a = safe_mod(a, b);if (a == 0) return {b, 0};long long s = b, t = a;long long m0 = 0, m1 = 1;while (t) {long long u = s / t;s -= t * u;m0 -= m1 * u;auto tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}if (m0 < 0) m0 += b / s;return {s, m0};}long long inv_mod(long long x, long long m) {assert(1 <= m);auto z = inv_gcd(x, m);assert(z.first == 1);return z.second;}std::pair<long long, long long> crt(const std::vector<long long>& r,const std::vector<long long>& m) {assert(r.size() == m.size());int n = int(r.size());long long r0 = 0, m0 = 1;for (int i = 0; i < n; i++) {assert(1 <= m[i]);long long r1 = safe_mod(r[i], m[i]), m1 = m[i];if (m0 < m1) {std::swap(r0, r1);std::swap(m0, m1);}if (m0 % m1 == 0) {if (r0 % m1 != r1) return {0, 0};continue;}long long g, im;std::tie(g, im) = inv_gcd(m0, m1);long long u1 = (m1 / g);if ((r1 - r0) % g) return {0, 0};long long x = (r1 - r0) / g % u1 * im % u1;r0 += x * m0;m0 *= u1;if (r0 < 0) r0 += m0;}return {r0, m0};}long long floor_sum(long long n, long long m, long long a, long long b) {long long ans = 0;if (a >= m) {ans += (n - 1) * n * (a / m) / 2;a %= m;}if (b >= m) {ans += n * (b / m);b %= m;}long long y_max = (a * n + b) / m, x_max = (y_max * m - b);if (y_max == 0) return ans;ans += (n - (x_max + a - 1) / a) * y_max;ans += floor_sum(y_max, a, m, (a - x_max % a) % a);return ans;}int main(){ios::sync_with_stdio(false);cin.tie(0);ll n, m, p, q;cin >> n >> m >> p >> q;while(q--){ll x, f;cin >> x >> f;auto pa = crt({0, f}, {x, p});if(pa.second == 0){cout << 0 << '\n';continue;}//a * x + bpa.first /= x;pa.second /= x;ll ans = (m - pa.first) / pa.second;//cerr << pa.first << " " << pa.second << '\n';if(m >= pa.first) ans++;if(pa.first == 0) ans--;ans = max(ans, 0ll);cout << ans << '\n';}}