/* -*- coding: utf-8 -*- * * 3527.cc: No.3527 Minimum Abs Sum - yukicoder */ #include #include #include using namespace std; /* constant */ const int MAX_N = 200000; const int MOD = 1000000007; const __int128_t L4INF = (__int128_t)1 << 90; /* typedef */ using ll = long long; using l4 = __int128_t; template struct MI { int v; MI(): v() {} MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; } MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; } explicit operator int() const { return v; } MI operator+(const MI m) const { return MI(v + m.v); } MI operator-(const MI m) const { return MI(v + MOD - m.v); } MI operator-() const { return MI(MOD - v); } MI operator*(const MI m) const { return MI((long long)v * m.v); } MI &operator+=(const MI m) { return (*this = *this + m); } MI &operator-=(const MI m) { return (*this = *this - m); } MI &operator*=(const MI m) { return (*this = *this * m); } bool operator==(const MI m) const { return v == m.v; } bool operator!=(const MI m) const { return v != m.v; } MI pow(int n) const { // a^n % MOD MI pm = 1, a = *this; while (n > 0) { if (n & 1) pm *= a; a *= a; n >>= 1; } return pm; } MI inv() const { return pow(MOD - 2); } MI operator/(const MI m) const { return *this * m.inv(); } MI &operator/=(const MI m) { return (*this = *this / m); } }; using mi = MI; template struct Frac { T n, d; Frac(): n(0), d(1) {} Frac(T _n): n(_n), d(1) {} Frac(T _n, T _d): n(_n), d(_d) { reduce(); } T __gcd(T m, T n) { // m >= 0, n >= 0 if (m < n) swap(m, n); while (n > 0) { T r = m % n; m = n; n = r; } return m; } void reduce() { if (d == 0) n = 0; else if (n == 0) d = 1; else { if (d < 0) n = -n, d = -d; T absn = (n >= 0) ? n : -n; T g = __gcd(absn, d); if (g > 1) n /= g, d /= g; } } bool operator<(const Frac &f) const { return n * f.d < f.n * d; } bool operator>(const Frac &f) const { return n * f.d > f.n * d; } bool operator==(const Frac &f) const { return n * f.d == f.n * d; } bool operator!=(const Frac &f) const { return n * f.d != f.n * d; } }; using pfi = pair,int>; /* global variables */ int as[MAX_N], bs[MAX_N]; pfi fis[MAX_N]; /* subroutines */ /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", as + i); for (int i = 0; i < n; i++) scanf("%d", bs + i); int m = 0; ll sa = 0, sb = 0; for (int i = 0; i < n; i++) { if (as[i] > 0) as[i] = -as[i], bs[i] = -bs[i]; if (as[i] != 0) { fis[m++] = {Frac(bs[i], as[i]), i}; sa += as[i], sb += bs[i]; } } sort(fis, fis + m); Frac miny(L4INF, 1); Frac minx; for (int i = 0; i < m; i++) { auto [xj, j] = fis[i]; //printf(" %d/%d, %d,%d\n", xj.n, xj.d, as[j], bs[j]); sa -= as[j] * 2, sb -= bs[j] * 2; ll xn = xj.n, xd = xj.d; // y = f(x) = sa*x-sb = sa*xn/xd-sb = (sa*xn-sb*xd)/xd Frac y((l4)sa * xn - (l4)sb * xd, xd); //printf(" i=%d: x=%lld/%lld, y=%lld/%lld\n", i, xj.n, xj.d, (ll)y.n, (ll)y.d); if (miny > y) miny = y, minx = xj; } mi ans = mi(minx.n) / mi(minx.d); printf("%d\n", (int)ans); return 0; }