QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235110#3084. Count Min Ratioalpha1022AC ✓386ms83980kbC++1410.6kb2023-11-02 14:20:072023-11-02 14:20:07

Judging History

你现在查看的是最新测评结果

  • [2023-11-02 14:20:07]
  • 评测
  • 测评结果:AC
  • 用时:386ms
  • 内存:83980kb
  • [2023-11-02 14:20:07]
  • 提交

answer

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using ll = long long;

using namespace std;

const int mod = 998244353;
inline int norm(int x) {
  return x >= mod ? x - mod : x;
}
inline int reduce(int x) {
  return x < 0 ? x + mod : x;
}
inline int neg(int x) {
  return x ? mod - x : 0;
}
inline void add(int &x, int y) {
  if ((x += y - mod) < 0)
    x += mod;
}
inline void sub(int &x, int y) {
  if ((x -= y) < 0)
    x += mod;
}
inline void fam(int &x, int y, int z) {
  x = (x + (ll)y * z) % mod;
}
inline int qpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1)
    (b & 1) && (ret = (ll)ret * a % mod),
    a = (ll)a * a % mod;
  return ret;
}

const int N = 1e6;

namespace Poly {
  const int LG = 20;
  const int N = 1 << LG + 1;
  const int G = 3;
  
  int lg2[N + 5];
  int fac[N + 5], ifac[N + 5], inv[N + 5];
  int rt[N + 5];
  
  inline void init() {
    for (int i = 2; i <= N; ++i)
      lg2[i] = lg2[i >> 1] + 1;
    rt[0] = 1, rt[1 << LG] = qpow(G, (mod - 1) >> LG + 2);
    for (int i = LG; i; --i)
      rt[1 << i - 1] = (ll)rt[1 << i] * rt[1 << i] % mod;
    for (int i = 1; i < N; ++i)
      rt[i] = (ll)rt[i & i - 1] * rt[i & -i] % mod;
    fac[0] = 1;
    for (int i = 1; i <= N; ++i)
      fac[i] = (ll)fac[i - 1] * i % mod;
    ifac[N] = qpow(fac[N], mod - 2);
    for (int i = N; i; --i)
      ifac[i - 1] = (ll)ifac[i] * i % mod;
    for (int i = 1; i <= N; ++i)
      inv[i] = (ll)ifac[i] * fac[i - 1] % mod;
  }
  
  struct poly {
    
    vector<int> a;
    inline poly(int x = 0) {
      if (x)
        a.push_back(x);
    }
    inline poly(const vector<int> &o) {
      a = o;
    }
    inline poly(const poly &o) {
      a = o.a;
    }
    
    inline int size() const {
      return a.size();
    }
    inline bool empty() const {
      return a.empty();
    }
    inline void resize(int x) {
      a.resize(x);
    }
    inline int operator[](int x) const {
      if (x < 0 || x >= size())
        return 0;
      return a[x];
    }
    inline void clear() {
      vector<int>().swap(a);
    }
    inline poly modxn(int n) const {
      if (a.empty())
        return poly();
      n = min(n, size());
      return poly(vector<int>(a.begin(), a.begin() + n));
    }
    inline poly rever() const {
      return poly(vector<int>(a.rbegin(), a.rend()));
    }
    
    inline void dif() {
      int n = size();
      for (int i = 0, len = n >> 1; len; ++i, len >>= 1)
        for (int j = 0, *w = rt; j < n; j += len << 1, ++w)
          for (int k = j; k < j + len; ++k) {
            int R = (ll)*w * a[k + len] % mod;
            a[k + len] = reduce(a[k] - R),
            add(a[k], R);
          }
    }
    inline void dit() {
      int n = size();
      for (int i = 0, len = 1; len < n; ++i, len <<= 1)
        for (int j = 0, *w = rt; j < n; j += len << 1, ++w)
          for (int k = j; k < j + len; ++k) {
            int R = norm(a[k] + a[k + len]);
            a[k + len] = (ll)*w * (a[k] - a[k + len] + mod) % mod,
            a[k] = R;
          }
      reverse(a.begin() + 1, a.end());
      for (int i = 0; i < n; ++i)
        a[i] = (ll)a[i] * inv[n] % mod;
    }
    inline void ntt(int type = 1) {
      type == 1 ? dif() : dit();
    }
    
    friend inline poly operator+(const poly &a, const poly &b) {
      vector<int> ret(max(a.size(), b.size()));
      for (int i = 0; i < ret.size(); ++i)
        ret[i] = norm(a[i] + b[i]);
      return poly(ret);
    }
    friend inline poly operator-(const poly &a, const poly &b) {
      vector<int> ret(max(a.size(), b.size()));
      for (int i = 0; i < ret.size(); ++i)
        ret[i] = reduce(a[i] - b[i]);
      return poly(ret);
    }
    friend inline poly operator*(poly a, poly b) {
      if (a.empty() || b.empty())
        return poly();
      if (a.size() < 40 || b.size() < 40) {
        if (a.size() > b.size())
          swap(a, b);
        poly ret;
        ret.resize(a.size() + b.size() - 1);
        for (int i = 0; i < ret.size(); ++i)
          for (int j = 0; j <= i && j < a.size(); ++j)
            ret.a[i] = (ret[i] + (ll)a[j] * b[i - j]) % mod;
        return ret;
      }
      int lim = 1, tot = a.size() + b.size() - 1;
      for (; lim < tot; lim <<= 1);
      a.resize(lim), b.resize(lim);
      a.ntt(), b.ntt();
      for (int i = 0; i < lim; ++i)
        a.a[i] = (ll)a[i] * b[i] % mod;
      a.ntt(-1), a.resize(tot);
      return a;
    }
    
    poly &operator+=(const poly &o) {
      resize(max(size(), o.size()));
      for (int i = 0; i < o.size(); ++i)
        add(a[i], o[i]);
      return *this;
    }
    poly &operator-=(const poly &o) {
      resize(max(size(), o.size()));
      for (int i = 0; i < o.size(); ++i)
        sub(a[i], o[i]);
      return *this;
    }
    poly &operator*=(poly o) {
      return (*this) = (*this) * o;
    }
    
    poly deriv() const {
      if (empty())
        return poly();
      vector<int> ret(size() - 1);
      for (int i = 0; i < size() - 1; ++i)
        ret[i] = (ll)(i + 1) * a[i + 1] % mod;
      return poly(ret);
    }
    poly integ() const {
      if (empty())
        return poly();
      vector<int> ret(size() + 1);
      for (int i = 0; i < size(); ++i)
        ret[i + 1] = (ll)a[i] * inv[i + 1] % mod;
      return poly(ret);
    }
    inline poly inver(int m) const {
      poly ret(qpow(a[0], mod - 2)), f, g;
      for (int k = 1; k < m;) {
        k <<= 1, f.resize(k), g.resize(k);
        for (int i = 0; i < k; ++i)
          f.a[i] = operator[](i), g.a[i] = ret[i];
        f.ntt(), g.ntt();
        for (int i = 0; i < k; ++i)
          f.a[i] = (ll)f[i] * g[i] % mod;
        f.ntt(-1);
        for (int i = 0; i < (k >> 1); ++i)
          f.a[i] = 0;
        f.ntt();
        for (int i = 0; i < k; ++i)
          f.a[i] = (ll)f[i] * g[i] % mod;
        f.ntt(-1);
        ret.resize(k);
        for (int i = (k >> 1); i < k; ++i)
          ret.a[i] = neg(f[i]);
      }
      return ret.modxn(m);
    }
    inline pair<poly, poly> div(poly o) const {
      if (size() < o.size())
        return make_pair(poly(), *this);
      poly f, g;
      f = (rever().modxn(size() - o.size() + 1) * o.rever().inver(size() - o.size() + 1))
          .modxn(size() - o.size() + 1).rever();
      g = (modxn(o.size() - 1) - o.modxn(o.size() - 1) * f.modxn(o.size() - 1)).modxn(o.size() - 1);
      return make_pair(f, g);
    }
    inline poly log(int m) const {
      return (deriv() * inver(m)).integ().modxn(m);
    }
    inline poly exp(int m) const {
      poly ret(1), iv, it, d = deriv(), itd, itd0, t1;
      if (m < 70) {
        ret.resize(m);
        for (int i = 1; i < m; ++i) {
          for (int j = 1; j <= i; ++j)
            ret.a[i] = (ret[i] + (ll)j * operator[](j) % mod * ret[i - j]) % mod;
          ret.a[i] = (ll)ret[i] * inv[i] % mod;
        }
        return ret;
      }
      for (int k = 1; k < m;) {
        k <<= 1;
        it.resize(k >> 1);
        for (int i = 0; i < (k >> 1); ++i)
          it.a[i] = ret[i];
        itd = it.deriv(), itd.resize(k >> 1);
        iv = ret.inver(k >> 1), iv.resize(k >> 1);
        it.ntt(), itd.ntt(), iv.ntt();
        for (int i = 0; i < (k >> 1); ++i)
          it.a[i] = (ll)it[i] * iv[i] % mod,
          itd.a[i] = (ll)itd[i] * iv[i] % mod;
        it.ntt(-1), itd.ntt(-1), sub(it.a[0], 1);
        for (int i = 0; i < k - 1; ++i)
          sub(itd.a[i % (k >> 1)], d[i]);
        itd0.resize((k >> 1) - 1);
        for (int i = 0; i < (k >> 1) - 1; ++i)
          itd0.a[i] = d[i];
        itd0 = (itd0 * it).modxn((k >> 1) - 1);
        t1.resize(k - 1);
        for (int i = (k >> 1) - 1; i < k - 1; ++i)
          t1.a[i] = itd[(i + (k >> 1)) % (k >> 1)];
        for (int i = k >> 1; i < k - 1; ++i)
          sub(t1.a[i], itd0[i - (k >> 1)]);
        t1 = t1.integ();
        for (int i = 0; i < (k >> 1); ++i)
          t1.a[i] = t1[i + (k >> 1)];
        for (int i = (k >> 1); i < k; ++i)
          t1.a[i] = 0;
        t1.resize(k >> 1), t1 = (t1 * ret).modxn(k >> 1), t1.resize(k);
        for (int i = (k >> 1); i < k; ++i)
          t1.a[i] = t1[i - (k >> 1)];
        for (int i = 0; i < (k >> 1); ++i)
          t1.a[i] = 0;
        ret -= t1;
      }
      return ret.modxn(m);
    }
    inline poly sqrt(int m) const {
      poly ret(1), f, g;
      for (int k = 1; k < m;) {
        k <<= 1;
        f = ret, f.resize(k >> 1);
        f.ntt();
        for (int i = 0; i < (k >> 1); ++i)
          f.a[i] = (ll)f[i] * f[i] % mod;
        f.ntt(-1);
        for (int i = 0; i < k; ++i)
          sub(f.a[i % (k >> 1)], operator[](i));
        g = (2 * ret).inver(k >> 1), f = (f * g).modxn(k >> 1), f.resize(k);
        for (int i = (k >> 1); i < k; ++i)
          f.a[i] = f[i - (k >> 1)];
        for (int i = 0; i < (k >> 1); ++i)
          f.a[i] = 0;
        ret -= f;
      }
      return ret.modxn(m);
    }
    inline poly pow(int m, int k1, int k2 = -1) const {
      if (empty())
        return poly();
      if (k2 == -1)
        k2 = k1;
      int t = 0;
      for (; t < size() && !a[t]; ++t);
      if ((ll)t * k1 >= m)
        return poly();
      poly ret;
      ret.resize(m);
      int u = qpow(a[t], mod - 2), v = qpow(a[t], k2);
      for (int i = 0; i < m - t * k1; ++i)
        ret.a[i] = (ll)operator[](i + t) * u % mod;
      ret = ret.log(m - t * k1);
      for (int i = 0; i < ret.size(); ++i)
        ret.a[i] = (ll)ret[i] * k1 % mod;
      ret = ret.exp(m - t * k1), t *= k1, ret.resize(m);
      for (int i = m - 1; i >= t; --i)
        ret.a[i] = (ll)ret[i - t] * v % mod;
      for (int i = 0; i < t; ++i)
        ret.a[i] = 0;
      return ret;
    }
  };
}
using Poly::fac;
using Poly::ifac;
using Poly::inv;
using Poly::init;
using Poly::poly;

inline int binom(int n, int m) {
  return n < m || m < 0 ? 0 : (ll)fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

ll r;
int b, n;
poly u, v;
int ans;
int main() {
  init();
  
  scanf("%lld%d", &r, &b), n = (r / b) % mod, r %= mod;
  u.resize(b + 2), v.resize(b + 2);
  for (int i = 0, p = 1; i <= b + 1; ++i)
    p = (ll)p * (n + 1) % mod,
    u.a[i] = (ll)p * ifac[i + 1] % mod,
    v.a[i] = ifac[i + 1];
  u = (u * v.inver(b + 2)).modxn(b + 2);
  for (int i = 0; i <= b + 1; ++i)
    u.a[i] = (ll)u[i] * fac[i] % mod;
  sub(u.a[0], 1);
  for (int i = 0, c = 1; i <= b; ++i)
    ans = (ans + ((r + 1) * u[b - i] + (ll)(mod - b) * u[b - i + 1]) % mod * c) % mod,
    c = c * (r + b + 1 - i) % mod * inv[i + 1] % mod;
  printf("%d\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 101ms
memory: 53992kb

input:

683378734395758315 236468

output:

977900314

result:

ok single line: '977900314'

Test #2:

score: 0
Accepted
time: 182ms
memory: 60932kb

input:

979090400467196153 358547

output:

272249768

result:

ok single line: '272249768'

Test #3:

score: 0
Accepted
time: 383ms
memory: 83612kb

input:

989388577384252441 976371

output:

177173344

result:

ok single line: '177173344'

Test #4:

score: 0
Accepted
time: 104ms
memory: 54076kb

input:

518112700506783575 241956

output:

326187036

result:

ok single line: '326187036'

Test #5:

score: 0
Accepted
time: 378ms
memory: 78596kb

input:

142225746666542457 762622

output:

169474298

result:

ok single line: '169474298'

Test #6:

score: 0
Accepted
time: 366ms
memory: 74328kb

input:

76682402966725409 589690

output:

742679145

result:

ok single line: '742679145'

Test #7:

score: 0
Accepted
time: 185ms
memory: 62540kb

input:

893084247022057423 436807

output:

792093980

result:

ok single line: '792093980'

Test #8:

score: 0
Accepted
time: 377ms
memory: 75164kb

input:

677057357948041903 621912

output:

566088487

result:

ok single line: '566088487'

Test #9:

score: 0
Accepted
time: 385ms
memory: 83100kb

input:

585185490292220209 960011

output:

395797373

result:

ok single line: '395797373'

Test #10:

score: 0
Accepted
time: 381ms
memory: 81180kb

input:

527128913915411756 864691

output:

626521264

result:

ok single line: '626521264'

Test #11:

score: 0
Accepted
time: 34ms
memory: 46632kb

input:

480275827542304693 60780

output:

208136653

result:

ok single line: '208136653'

Test #12:

score: 0
Accepted
time: 374ms
memory: 79104kb

input:

38401586484842791 782406

output:

445127574

result:

ok single line: '445127574'

Test #13:

score: 0
Accepted
time: 166ms
memory: 61516kb

input:

274389276438594725 392173

output:

336742756

result:

ok single line: '336742756'

Test #14:

score: 0
Accepted
time: 97ms
memory: 54000kb

input:

537410974978749538 246828

output:

8231958

result:

ok single line: '8231958'

Test #15:

score: 0
Accepted
time: 184ms
memory: 58568kb

input:

651479222208992250 265311

output:

147181253

result:

ok single line: '147181253'

Test #16:

score: 0
Accepted
time: 104ms
memory: 52916kb

input:

242868802681182462 189137

output:

572588508

result:

ok single line: '572588508'

Test #17:

score: 0
Accepted
time: 369ms
memory: 73796kb

input:

408214018246265459 560647

output:

686897443

result:

ok single line: '686897443'

Test #18:

score: 0
Accepted
time: 362ms
memory: 74648kb

input:

44121777270056545 599614

output:

319069814

result:

ok single line: '319069814'

Test #19:

score: 0
Accepted
time: 174ms
memory: 61148kb

input:

610290521186765100 365864

output:

5012106

result:

ok single line: '5012106'

Test #20:

score: 0
Accepted
time: 56ms
memory: 47884kb

input:

907257322745121966 65555

output:

330906285

result:

ok single line: '330906285'

Test #21:

score: 0
Accepted
time: 62ms
memory: 49448kb

input:

995630373529096980 128131

output:

363172456

result:

ok single line: '363172456'

Test #22:

score: 0
Accepted
time: 41ms
memory: 46456kb

input:

478531585013359623 45327

output:

489805295

result:

ok single line: '489805295'

Test #23:

score: 0
Accepted
time: 377ms
memory: 78736kb

input:

289220686690167539 762823

output:

931142647

result:

ok single line: '931142647'

Test #24:

score: 0
Accepted
time: 370ms
memory: 73900kb

input:

956128385648436543 564939

output:

327546179

result:

ok single line: '327546179'

Test #25:

score: 0
Accepted
time: 365ms
memory: 77340kb

input:

268987821611568675 714871

output:

681256386

result:

ok single line: '681256386'

Test #26:

score: 0
Accepted
time: 179ms
memory: 60556kb

input:

41530899487998973 344498

output:

450296001

result:

ok single line: '450296001'

Test #27:

score: 0
Accepted
time: 371ms
memory: 78964kb

input:

443735410834630537 772631

output:

684658654

result:

ok single line: '684658654'

Test #28:

score: 0
Accepted
time: 380ms
memory: 80012kb

input:

951396959824268572 830986

output:

65374615

result:

ok single line: '65374615'

Test #29:

score: 0
Accepted
time: 182ms
memory: 63712kb

input:

727656794203823997 488995

output:

445963467

result:

ok single line: '445963467'

Test #30:

score: 0
Accepted
time: 372ms
memory: 74940kb

input:

711635850174145854 608033

output:

385604773

result:

ok single line: '385604773'

Test #31:

score: 0
Accepted
time: 371ms
memory: 79712kb

input:

958593486141334376 811645

output:

716353950

result:

ok single line: '716353950'

Test #32:

score: 0
Accepted
time: 96ms
memory: 53408kb

input:

876169953712419552 212745

output:

741644191

result:

ok single line: '741644191'

Test #33:

score: 0
Accepted
time: 182ms
memory: 61604kb

input:

637173299850560942 377037

output:

643853630

result:

ok single line: '643853630'

Test #34:

score: 0
Accepted
time: 373ms
memory: 83156kb

input:

845819889032839962 960360

output:

300421637

result:

ok single line: '300421637'

Test #35:

score: 0
Accepted
time: 178ms
memory: 60164kb

input:

858157800928362508 336636

output:

317266260

result:

ok single line: '317266260'

Test #36:

score: 0
Accepted
time: 376ms
memory: 81948kb

input:

621886439901466850 913233

output:

62587572

result:

ok single line: '62587572'

Test #37:

score: 0
Accepted
time: 191ms
memory: 64692kb

input:

19793600863167987 523130

output:

454747537

result:

ok single line: '454747537'

Test #38:

score: 0
Accepted
time: 24ms
memory: 44940kb

input:

800097659409521417 2735

output:

498367926

result:

ok single line: '498367926'

Test #39:

score: 0
Accepted
time: 376ms
memory: 73464kb

input:

96718659537798620 549821

output:

104440627

result:

ok single line: '104440627'

Test #40:

score: 0
Accepted
time: 380ms
memory: 82036kb

input:

512381071437748587 910502

output:

768449929

result:

ok single line: '768449929'

Test #41:

score: 0
Accepted
time: 368ms
memory: 79640kb

input:

678834243213393 813374

output:

374395787

result:

ok single line: '374395787'

Test #42:

score: 0
Accepted
time: 374ms
memory: 73368kb

input:

33363233875471439 545561

output:

610128530

result:

ok single line: '610128530'

Test #43:

score: 0
Accepted
time: 98ms
memory: 52316kb

input:

179544154312981642 175883

output:

187932725

result:

ok single line: '187932725'

Test #44:

score: 0
Accepted
time: 386ms
memory: 83980kb

input:

696386454207742585 999005

output:

127047882

result:

ok single line: '127047882'

Test #45:

score: 0
Accepted
time: 357ms
memory: 79908kb

input:

610761556176970731 826320

output:

126494438

result:

ok single line: '126494438'

Test #46:

score: 0
Accepted
time: 65ms
memory: 48224kb

input:

282015621243753190 69441

output:

196294929

result:

ok single line: '196294929'

Test #47:

score: 0
Accepted
time: 183ms
memory: 61696kb

input:

84137964725034228 399086

output:

362319233

result:

ok single line: '362319233'

Test #48:

score: 0
Accepted
time: 354ms
memory: 78028kb

input:

397211021773266000 742250

output:

792606046

result:

ok single line: '792606046'

Test #49:

score: 0
Accepted
time: 93ms
memory: 51692kb

input:

544716383493341413 138950

output:

789809654

result:

ok single line: '789809654'

Test #50:

score: 0
Accepted
time: 172ms
memory: 63988kb

input:

169266483579812352 492569

output:

896396610

result:

ok single line: '896396610'

Test #51:

score: 0
Accepted
time: 369ms
memory: 77028kb

input:

999961057870786440 690363

output:

721544361

result:

ok single line: '721544361'

Test #52:

score: 0
Accepted
time: 370ms
memory: 82172kb

input:

278829653591349043 916814

output:

836880873

result:

ok single line: '836880873'

Test #53:

score: 0
Accepted
time: 366ms
memory: 74320kb

input:

210453150703882029 586356

output:

90787821

result:

ok single line: '90787821'

Test #54:

score: 0
Accepted
time: 359ms
memory: 83548kb

input:

184805922528049560 979882

output:

15187856

result:

ok single line: '15187856'

Test #55:

score: 0
Accepted
time: 184ms
memory: 62468kb

input:

564625421256646746 426949

output:

500082355

result:

ok single line: '500082355'

Test #56:

score: 0
Accepted
time: 364ms
memory: 76720kb

input:

732940561153051407 681732

output:

564670938

result:

ok single line: '564670938'

Test #57:

score: 0
Accepted
time: 367ms
memory: 75140kb

input:

116171740890278055 607634

output:

401012094

result:

ok single line: '401012094'

Test #58:

score: 0
Accepted
time: 178ms
memory: 61092kb

input:

805967230765387304 361535

output:

981172185

result:

ok single line: '981172185'

Test #59:

score: 0
Accepted
time: 54ms
memory: 48804kb

input:

442286081725079290 102140

output:

945328644

result:

ok single line: '945328644'

Test #60:

score: 0
Accepted
time: 183ms
memory: 60252kb

input:

593100620083622655 328979

output:

26517397

result:

ok single line: '26517397'

Test #61:

score: 0
Accepted
time: 377ms
memory: 82264kb

input:

369228649216946434 923981

output:

967449549

result:

ok single line: '967449549'

Test #62:

score: 0
Accepted
time: 188ms
memory: 64512kb

input:

867097686907691811 520338

output:

311001250

result:

ok single line: '311001250'

Test #63:

score: 0
Accepted
time: 168ms
memory: 60588kb

input:

970618223153396863 346325

output:

920370317

result:

ok single line: '920370317'

Test #64:

score: 0
Accepted
time: 371ms
memory: 82024kb

input:

938112313632104905 916660

output:

801817210

result:

ok single line: '801817210'

Test #65:

score: 0
Accepted
time: 183ms
memory: 63316kb

input:

445439139973740572 466762

output:

218747502

result:

ok single line: '218747502'

Test #66:

score: 0
Accepted
time: 186ms
memory: 61552kb

input:

642177853459241805 399086

output:

961758742

result:

ok single line: '961758742'

Test #67:

score: 0
Accepted
time: 27ms
memory: 45024kb

input:

315967632725600222 12109

output:

244881715

result:

ok single line: '244881715'

Test #68:

score: 0
Accepted
time: 178ms
memory: 60616kb

input:

290180569836470426 350636

output:

82758012

result:

ok single line: '82758012'

Test #69:

score: 0
Accepted
time: 103ms
memory: 52980kb

input:

219861379687179110 198893

output:

906025950

result:

ok single line: '906025950'

Test #70:

score: 0
Accepted
time: 97ms
memory: 53376kb

input:

314286634957673330 204928

output:

611659493

result:

ok single line: '611659493'

Test #71:

score: 0
Accepted
time: 106ms
memory: 52256kb

input:

141833982443113896 173643

output:

25787351

result:

ok single line: '25787351'

Test #72:

score: 0
Accepted
time: 374ms
memory: 83980kb

input:

656293290102168163 990715

output:

375890945

result:

ok single line: '375890945'

Test #73:

score: 0
Accepted
time: 36ms
memory: 45412kb

input:

795787394303445639 26120

output:

703297448

result:

ok single line: '703297448'

Test #74:

score: 0
Accepted
time: 175ms
memory: 58980kb

input:

404516778708210183 278693

output:

754235281

result:

ok single line: '754235281'

Test #75:

score: 0
Accepted
time: 371ms
memory: 83104kb

input:

815752358214716192 954803

output:

624809890

result:

ok single line: '624809890'

Test #76:

score: 0
Accepted
time: 366ms
memory: 77480kb

input:

6033256690046915 721561

output:

15093794

result:

ok single line: '15093794'

Test #77:

score: 0
Accepted
time: 376ms
memory: 78856kb

input:

229123183682627129 781800

output:

614606849

result:

ok single line: '614606849'

Test #78:

score: 0
Accepted
time: 360ms
memory: 77876kb

input:

45500860931655609 734639

output:

414234307

result:

ok single line: '414234307'

Test #79:

score: 0
Accepted
time: 373ms
memory: 77544kb

input:

411143153580195786 717525

output:

869882027

result:

ok single line: '869882027'

Test #80:

score: 0
Accepted
time: 187ms
memory: 60548kb

input:

837981964676080593 350729

output:

971717274

result:

ok single line: '971717274'

Test #81:

score: 0
Accepted
time: 375ms
memory: 76856kb

input:

104580223797803755 687802

output:

89986728

result:

ok single line: '89986728'

Test #82:

score: 0
Accepted
time: 186ms
memory: 64180kb

input:

43929905834825307 500678

output:

41001420

result:

ok single line: '41001420'

Test #83:

score: 0
Accepted
time: 53ms
memory: 49292kb

input:

659029063626506522 115342

output:

549415725

result:

ok single line: '549415725'

Test #84:

score: 0
Accepted
time: 379ms
memory: 81612kb

input:

975527438656796764 896996

output:

335298357

result:

ok single line: '335298357'

Test #85:

score: 0
Accepted
time: 45ms
memory: 46260kb

input:

41903412710012308 44339

output:

459070475

result:

ok single line: '459070475'

Test #86:

score: 0
Accepted
time: 184ms
memory: 64144kb

input:

199728788856097743 506539

output:

716828027

result:

ok single line: '716828027'

Test #87:

score: 0
Accepted
time: 378ms
memory: 76772kb

input:

421541678045878439 688271

output:

94569400

result:

ok single line: '94569400'

Test #88:

score: 0
Accepted
time: 200ms
memory: 64060kb

input:

791034501231194792 493676

output:

22349450

result:

ok single line: '22349450'

Test #89:

score: 0
Accepted
time: 377ms
memory: 83604kb

input:

514029786760975442 975431

output:

920960941

result:

ok single line: '920960941'

Test #90:

score: 0
Accepted
time: 182ms
memory: 63624kb

input:

615289178558364244 476243

output:

924051936

result:

ok single line: '924051936'

Test #91:

score: 0
Accepted
time: 376ms
memory: 76288kb

input:

402536439938086115 666553

output:

414913820

result:

ok single line: '414913820'

Test #92:

score: 0
Accepted
time: 183ms
memory: 63368kb

input:

407450809830779802 471059

output:

898345043

result:

ok single line: '898345043'

Test #93:

score: 0
Accepted
time: 361ms
memory: 80096kb

input:

54203387312776409 831213

output:

395210033

result:

ok single line: '395210033'

Test #94:

score: 0
Accepted
time: 36ms
memory: 45440kb

input:

989065424860678110 31896

output:

217306385

result:

ok single line: '217306385'

Test #95:

score: 0
Accepted
time: 178ms
memory: 60456kb

input:

867310479829046576 338035

output:

429174354

result:

ok single line: '429174354'

Test #96:

score: 0
Accepted
time: 176ms
memory: 58764kb

input:

749559649873639195 262837

output:

582660834

result:

ok single line: '582660834'

Test #97:

score: 0
Accepted
time: 371ms
memory: 82164kb

input:

353931598778126361 908992

output:

102642620

result:

ok single line: '102642620'

Test #98:

score: 0
Accepted
time: 185ms
memory: 63092kb

input:

294477693266176644 462263

output:

694707454

result:

ok single line: '694707454'

Test #99:

score: 0
Accepted
time: 378ms
memory: 80296kb

input:

428019413841133868 832595

output:

114075344

result:

ok single line: '114075344'

Test #100:

score: 0
Accepted
time: 97ms
memory: 51668kb

input:

660115115462352421 146580

output:

390845669

result:

ok single line: '390845669'