結果
問題 | No.2324 Two Countries within UEC |
ユーザー |
![]() |
提出日時 | 2023-05-28 13:51:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,173 bytes |
コンパイル時間 | 1,907 ms |
コンパイル使用メモリ | 167,004 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-26 22:04:45 |
合計ジャッジ時間 | 9,109 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 WA * 11 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long int ll;typedef pair<ll,ll> P;typedef vector<ll> VI;typedef vector<VI> VVI;#define REP(i,n) for(int i=0;i<(n);i++)#define ALL(v) v.begin(),v.end()template<typename T> bool chmax(T& x, const T& y){return (x<y)?(x=y,true):false;};template<typename T> bool chmin(T& x, const T& y){return (x>y)?(x=y,true):false;};constexpr ll MOD=998244353;constexpr ll INF=2e18;ll extgcd(ll a, ll b, ll &x, ll &y) {if(b==0){x=1;y=0;return a;}ll gcd=extgcd(b,a%b,x,y);ll oldX=x;x=y;y=oldX-a/b*y;return gcd;}P crt2(ll b1, ll m1, ll b2, ll m2){ll x, y;ll d=extgcd(m1,m2,x,y);if((b2-b1)%d!=0)return {0,-1};else{ll m=m1*(m2/d);return {((b1+((b2-b1)/d)*x%(m2/d)*m1)%m+m)%m,m};}}int main(){ll n, m, p, q;cin >> n >> m >> p >> q;ll x, f;REP(i,q){cin >> x >> f;P r=crt2(f,p,0,x);if(r.first==-1||r.first/x>m)cout << 0 << endl;else{ll k=m-r.first/x;cout << k/p+(r.first!=0) << endl;}}return 0;}