結果
問題 |
No.3307 Almost Equal
|
ユーザー |
![]() |
提出日時 | 2025-10-18 21:18:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 2,212 bytes |
コンパイル時間 | 3,231 ms |
コンパイル使用メモリ | 279,740 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-10-18 21:18:40 |
合計ジャッジ時間 | 5,436 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <iostream> using namespace std; typedef long long ll; template <typename T = long long> T floor_sum(T n, T m, T a, T b) { T ans = 0; if (m < 0) { m = -m; a = -a; b = -b; } if (a < 0) { T a2 = (a % m + m) % m; ans -= (n - 1) * n * ((a2 - a) / m) / 2; a = a2; } if (b < 0) { T b2 = (b % m + m) % m; ans -= n * ((b2 - b) / m); b = b2; } if (a >= m) { ans += (n - 1) * n * (a / m) / 2; a %= m; } if (b >= m) { ans += n * (b / m); b %= m; } T y_max = a * (n - 1) + b; if (y_max < m) return ans; return ans + floor_sum((a * n + b) / m, a, m, (a * n + b) % m); } template <typename T = long long> T ceil_sum(T n,T m,T a,T b){ return floor_sum<T>(n,m,a,b + m - 1); } // int128入出力用ライブラリ // copied from: https://kenkoooo.hatenablog.com/entry/2016/11/30/163533 #include <bits/stdc++.h> using namespace std; std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while (tmp != 0); if (value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if (dest.rdbuf()->sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } __int128 parse(string &s) { __int128 ret = 0; for (int i = 0; i < s.length(); i++) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0'; return ret; } typedef __int128 i128; int main(){ ll a,b,c,d; cin >> a >> b >> c >> d; if(a*d==b*c){ cout << -1 << "\n"; return 0; } if(a*d>b*c){ swap(a,c); swap(b,d); } // a/b < c/d // round(ai/b)==round(ci/d)==xごとに数える i128 A = a,B = b,C = c,D = d; // x==0 i128 ans = (D + 2*C - 1)/(2*C); i128 E = (A*D + B*C)/(2*(B*C - D*A)); ans += ceil_sum<i128>(E,2*C,2*D,3*D); ans -= ceil_sum<i128>(E,2*A,2*B,B); // i==0をcountしている ans--; cout << ans << "\n"; }