結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
|
提出日時 | 2021-01-22 22:22:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,788 bytes |
コンパイル時間 | 1,849 ms |
コンパイル使用メモリ | 196,248 KB |
最終ジャッジ日時 | 2025-01-18 04:34:04 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 TLE * 2 |
ソースコード
/*** author: yuji9511 ***/#include <bits/stdc++.h>// #include <atcoder/all>// using namespace atcoder;using namespace std;using ll = long long;using lpair = pair<ll, ll>;using vll = vector<ll>;const ll MOD = 1e9+7;const ll INF = 1e18;#define rep(i,m,n) for(ll i=(m);i<(n);i++)#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)ostream& operator<<(ostream& os, lpair& h){ os << "(" << h.first << ", " << h.second << ")"; return os;}#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};void print() {}template <class H,class... T>void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}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;}void solve(){ll A,B,C,N;cin >> A >> B >> C >> N;ll a[3];a[0] = A; a[1] = B; a[2] = C;sort(a,a+3);A = a[0]; B = a[1]; C = a[2];ll ans = 0;ll g = gcd(A,B);A /= g; B /= g;for(ll c = 0; c * C <= N; c++){ll amari = N - c * C;// Ax + By = amariif(amari % g != 0) continue;ll x,y;extgcd(A, B, x, y);x *= amari / g;y *= amari / g;// print(A/g,B/g,amari,x,y);ll k_max = 0;if(x >= 0){k_max = x / B;}else{k_max = -1 * ((abs(x) + B-1) / B);}ll k_min = 0;if(y >= 0){k_min = -1 * (y / A);}else{k_min = (abs(y) + A-1) / A;}ll res = max(0LL, k_max - k_min + 1);ans += res;ans %= MOD;}print(ans);}int main(){cin.tie(0);ios::sync_with_stdio(false);ll t;cin >> t;while(t--) solve();}