結果
問題 | 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 long 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; } 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; } }