This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#define PROBLEM "https://yukicoder.me/problems/4459" #include "../template.hpp" #include "../Math/ceil_floor.hpp" template< typename T > inline T extgcd(T a, T b, T &x, T &y) { T d = a; if(b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } vector<ll> ve(3); void solve(){ cin>>ve; ll y;cin>>y; sort(ALL(ve)); ll a,b,c; a=ve[2],b=ve[1],c=ve[0]; ll res=0; ll g=gcd(b,c); ll j,k; ll u=b/g,v=c/g; ll gg=extgcd(u,v,j,k); for(ll i=0;i<=y;i+=a){ ll t=y-i; if(t%g) continue; t/=g; ll w=t/gg; // t=g*w // g=j*u+k*v; ll jj=j*w,kk=k*w; // j=j' + x * v // k=k' - x * u jj*=-1; ll dw=div_ceil(jj,v); ll up=div_floor(kk,u); // cout<<up<<" ~ "<<dw<<endl; res+=max(0ll,(up-dw+1)); if(res>=mod) res%=1000000007ll; } cout<<res<<"\n"; } signed main(){ int q;cin>>q; while(q--) solve(); return 0; }
#line 1 "test/yuki4459.test.cpp" #define PROBLEM "https://yukicoder.me/problems/4459" #line 1 "template.hpp" #include<bits/stdc++.h> using namespace std; #define ALL(x) begin(x),end(x) #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define mod 1000000007 using ll=long long; const int INF=1000000000; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct IOSetup{ IOSetup(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(12); } } iosetup; template<typename T> ostream &operator<<(ostream &os,const vector<T>&v){ for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" "); return os; } template<typename T> istream &operator>>(istream &is,vector<T>&v){ for(T &x:v)is>>x; return is; } #line 4 "test/yuki4459.test.cpp" #line 1 "Math/ceil_floor.hpp" // round for +inf template<typename INT> inline INT div_ceil(INT x,INT y){ return (x<0?x/y:(x+y-1)/y); } // round for -inf template<typename INT> inline INT div_floor(INT x,INT y){ return (x>0?x/y:(x-y+1)/y); } #line 6 "test/yuki4459.test.cpp" template< typename T > inline T extgcd(T a, T b, T &x, T &y) { T d = a; if(b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } vector<ll> ve(3); void solve(){ cin>>ve; ll y;cin>>y; sort(ALL(ve)); ll a,b,c; a=ve[2],b=ve[1],c=ve[0]; ll res=0; ll g=gcd(b,c); ll j,k; ll u=b/g,v=c/g; ll gg=extgcd(u,v,j,k); for(ll i=0;i<=y;i+=a){ ll t=y-i; if(t%g) continue; t/=g; ll w=t/gg; // t=g*w // g=j*u+k*v; ll jj=j*w,kk=k*w; // j=j' + x * v // k=k' - x * u jj*=-1; ll dw=div_ceil(jj,v); ll up=div_floor(kk,u); // cout<<up<<" ~ "<<dw<<endl; res+=max(0ll,(up-dw+1)); if(res>=mod) res%=1000000007ll; } cout<<res<<"\n"; } signed main(){ int q;cin>>q; while(q--) solve(); return 0; }