結果
問題 | No.2324 Two Countries within UEC |
ユーザー |
![]() |
提出日時 | 2023-05-28 14:56:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 270 ms / 2,000 ms |
コード長 | 842 bytes |
コンパイル時間 | 1,897 ms |
コンパイル使用メモリ | 194,428 KB |
最終ジャッジ日時 | 2025-02-13 12:16:25 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long longlong 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;}signed main(){int N,M,P,Q;cin>>N>>M>>P>>Q;for(int i=0;i<Q;i++){int x,t;cin>>x>>t;x %= P;int p = P;int z = gcd(p,x);if(t%z != 0){cout<<0<<endl;continue;}p /= z;x /= z;if(p == 1){cout<<M<<endl;continue;}int k = modinv(x,p)*t%p;if(t == 0){cout<<M/p<<endl;continue;}if(k+10*p >= M){int ans = 0;while(k <= M){ans++;k += p;}cout<<ans<<endl;continue;}cout<<max(0ll,(M+(p-k))/p)<<endl;}}