結果
問題 | No.2324 Two Countries within UEC |
ユーザー |
|
提出日時 | 2023-05-28 15:19:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 277 ms / 2,000 ms |
コード長 | 1,972 bytes |
コンパイル時間 | 922 ms |
コンパイル使用メモリ | 85,032 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 23:24:58 |
合計ジャッジ時間 | 7,884 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 |
ソースコード
#include<iostream>#include<set>#include<algorithm>#include<vector>#include<string>#include<set>#include<map>#include<numeric>#include<queue>#include<tuple>#include<cmath>using namespace std;typedef long long ll;const ll INF=1LL<<60;typedef pair<int,int> P;typedef pair<int,P> PP;const ll MOD=998244353;/*tuple<ll,ll,ll> extgcd(ll a,ll b){if(b==0){return make_tuple(a,1,0);}else{auto [g,x,y]=extgcd(b,a%b);return make_tuple(g,y,x-(a/b)*y);}}mod_inv(ll a,ll p){extgcd(a,p);}*///拡張ユークリッド互除法long long int ext_gcd(long long int a, long long int b, long long int &x, long long int &y){if (b == 0){x = 1;y = 0;return a;}long long int q = a / b;long long int g = ext_gcd(b, a-q*b, x, y);long long int z = x-q*y;x = y;y = z;return g;}//aとmは互いに素, a^(-1) mod mlong long int modinv(long long int a, long long int m){long long int x, y;ext_gcd(a, m, x, y);x %= m;if (x < 0)x += m;return x;}ll gcd(ll x,ll y){return (y==0?x:gcd(y,x%y));}int main(){ll N,M,P,Q;cin>>N>>M>>P>>Q;vector<ll> ans(Q);ll xi,fi;for(int q=0;q<Q;q++){cin>>xi>>fi;ll g=gcd(xi,P);//cout<<"g="<<g<<endl;//xiのmod Pでの逆元if(fi%g!=0){//cout<<"tt"<<endl;ans[q]=0;}else{fi/=g;xi/=g;ll p=P/g;ll invxi=modinv(xi,p);ll tmp=fi*invxi%p;//cout<<"tmp="<<tmp<<endl;if(M-tmp<0){ans[q]=0;}else{//ll n;if(tmp==0){n=(M-tmp)/p;}else{n=(M-tmp)/p+1;}ans[q]=n;}}}for(ll v:ans){cout<<v<<endl;}}