結果
問題 | No.1358 [Zelkova 2nd Tune *] 語るなら枚数を... |
ユーザー |
|
提出日時 | 2021-01-23 09:04:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 786 ms / 2,000 ms |
コード長 | 1,458 bytes |
コンパイル時間 | 1,082 ms |
コンパイル使用メモリ | 96,832 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-30 01:47:58 |
合計ジャッジ時間 | 6,083 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream>#include <string>#include <algorithm>#include <vector>#include <iomanip>#include <cmath>#include <stdio.h>#include <queue>#include <deque>#include <cstdio>#include <set>#include <map>#include <bitset>#include <stack>#include <cctype>using namespace std;long long const mod = 1000000007;long long gcd(long long a, long long b) {if (a % b == 0) {return (b);}else {return (gcd(b, a % b));}}long long extGCD(long long a, long long b, long long& x, long long& 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;}int main(){int t;cin >> t;for (int i = 0; i < t; i++) {long long n, k, h, y;long long a[3];cin >> a[0] >> a[1] >> a[2] >> y;sort(a, a + 3);n = a[2], k = a[1], h = a[0];long long g = gcd(k, h);long long ans = 0, K, H, l, K1, H1, now = y;extGCD(k, h, K, H);long long mK = K, mH = H;for (int j = 0; j <= y / n; j++) {if (now % g == 0){K *= now / g, H *= now / g;l = k * h / g;K1 = l / k;H1 = l / h;if (K < 0) {H -= (-K + K1 - 1) / K1 * H1;K += (-K + K1 - 1) / K1 * K1;}else if (H < 0) {K -= (-H + H1 - 1) / H1 * K1;H += (-H + H1 - 1) / H1 * H1;}if (K >= 0 && H >= 0) {ans += K / K1 + H / H1 + 1;if (ans > mod) {ans %= mod;}}}now -= n;K = mK, H = mH;}cout << ans << endl;}}