結果

問題 No.2324 Two Countries within UEC
ユーザー t98slider
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 + b
pa.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';
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0