結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
![]() |
提出日時 | 2021-01-22 23:10:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 575 ms / 2,000 ms |
コード長 | 882 bytes |
コンパイル時間 | 902 ms |
コンパイル使用メモリ | 79,796 KB |
最終ジャッジ日時 | 2025-01-18 05:46:17 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include<algorithm> #include<cassert> #include<iostream> #include<vector> using namespace std; typedef long long lint; typedef vector<int>vi; typedef vector<lint>vl; typedef pair<int,int>pii; #define rep(i,n)for(int i=0;i<(int)(n);++i) lint gcd(lint x,lint y,lint&a,lint&b){ if(y==0){ a=1,b=0; return x; } lint q=x/y; lint g=gcd(y,x-q*y,b,a); b-=q*a; return g; } int main(){ int t;cin>>t; while(t--){ lint y;vl a(3); rep(i,3)cin>>a[i]; cin>>y; sort(a.rbegin(),a.rend()); lint ans=0; lint d,e; lint g=gcd(a[1],a[2],d,e); a[1]/=g; a[2]/=g; d%=a[2]; if(d<0)d+=a[2]; for(lint i=0;i<=y/a[0];i++){ lint c=y-a[0]*i; if(c%g)continue; c/=g; lint x=d*c%a[2]; if(c<x*a[1])continue; lint f=(c-x*a[1])/a[1]/a[2]; ans+=f+1; ans%=1000000007; } cout<<ans<<endl; } }