結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
![]() |
提出日時 | 2021-01-23 18:19:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 882 ms / 2,000 ms |
コード長 | 1,976 bytes |
コンパイル時間 | 1,228 ms |
コンパイル使用メモリ | 90,712 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-31 09:07:17 |
合計ジャッジ時間 | 5,987 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream>#include <string>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <list>#include <iterator>#include <cassert>#include <numeric>#include <functional>#include <ctime>#pragma warning(disable:4996)//#define ATCODER#ifdef ATCODER#include <atcoder/all>#endiftypedef long long ll;typedef unsigned long long ull;#define LINF 9223300000000000000#define LINF2 1223300000000000000#define LINF3 1000000000000#define INF 2140000000const long long MOD = 1000000007;//const long long MOD = 998244353;using namespace std;#ifdef ATCODERusing namespace atcoder;#endif// ax+by=gcd(a,b)を満たす(x, y)を返すll extGCD(ll a, ll b, ll &x, ll &y) {if (b == 0) {x = 1;y = 0;return a;}long long d = extGCD(b, a%b, y, x);y -= a / b * x;return d;}void solve(){ll A, B, C, Y;scanf("%lld%lld%lld%lld", &A, &B, &C, &Y);if (B < C)swap(B, C);if (A < B)swap(A, B);ll ans = 0;ll i, x0, y0;ll g = extGCD(B, C, x0, y0);for (i = 0; i <= Y; i += A) {ll tmp = Y - i;if (tmp%g==0) {ll B2 = B/g;ll C2 = C/g;ll x = x0 * tmp / g;ll y = y0 * tmp / g;if (x < 0) {ll t = (-x) / C2 +1;x += C2 * t;y -= B2 * t;}if (x >= 0) {ll t = x / C2;x -= C2 * t;y += B2 * t;}if (y < 0) continue;ll ans0 = y / B2 +1;ans = (ans + ans0)%MOD;}}printf("%lld\n", ans);return;}int main(){#if 0solve();#elseint T, t;scanf("%d",&T);for (t = 0; t < T; t++) {//cout << "Case #" << t + 1 << ": ";solve();}#endifreturn 0;}