結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
![]() |
提出日時 | 2021-01-23 00:32:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 440 ms / 2,000 ms |
コード長 | 1,008 bytes |
コンパイル時間 | 1,902 ms |
コンパイル使用メモリ | 195,080 KB |
最終ジャッジ日時 | 2025-01-18 06:56:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#define rep(i,n) for(int i=0;i<(int)(n);i++)#define ALL(v) v.begin(),v.end()typedef long long ll;#include <bits/stdc++.h>using namespace std;const int MOD=1e9+7;ll extGCD(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll d=extGCD(b,a%b,y,x);y-=a/b*x;return d;}int main(){int t;cin>>t;while(t--){ll n,k,h,y;cin>>n>>k>>h>>y;if(n>h) swap(n,h);if(k>h) swap(k,h);if(n>k) swap(n,k);int g=gcd(n,k);int ans=0;ll a=n/g;ll b=k/g;ll e,f;if(extGCD(a,b,e,f)<0) e=-e,f=-f;for(int i=0;i<=y/h;i++){if((y-h*i)%g!=0) continue;ll r=(y-h*i)/g;ll p=e*r;ll q=f*r;if(q/a<-p/b) continue;if(p<=0){ans=(ans+q/a+p/b)%MOD;if(p%b==0) ans++;}else if(q<=0){ans=(ans+q/a+p/b)%MOD;if(q%a==0) ans++;}else{ans=(ans+q/a+p/b+1)%MOD;}}cout<<ans<<endl;}return 0;}