| 93 | carry /= intx::radix; } } |
| 94 | return c.normalize(sign * b.sign); } |
| 95 | friend pair<intx,intx> divmod(const intx& n, const intx& d) { |
| 96 | assert(!(d.size() == 1 && d.data[0] == 0)); |
| 97 | intx q, r; q.data.assign(n.size(), 0); |
| 98 | for (int i = n.size() - 1; i >= 0; i--) { |
| 99 | r.data.insert(r.data.begin(), 0); |
| 100 | r = r + n.data[i]; |
| 101 | long long k = 0; |
| 102 | if (d.size() < r.size()) |
| 103 | k = (long long)intx::radix * r.data[d.size()]; |
| 104 | if (d.size() - 1 < r.size()) k += r.data[d.size() - 1]; |
| 105 | k /= d.data.back(); |
| 106 | r = r - abs(d) * k; |
| 107 | // if (r < 0) for (ll t = 1LL << 62; t >= 1; t >>= 1) { |
| 108 | // intx dd = abs(d) * t; |
| 109 | // while (r + dd < 0) r = r + dd, k -= t; } |
| 110 | while (r < 0) r = r + abs(d), k--; |
| 111 | q.data[i] = k; } |
| 112 | return pair<intx, intx>(q.normalize(n.sign * d.sign), r); } |
| 113 | intx operator /(const intx& d) const { |
| 114 | return divmod(*this,d).first; } |
| 115 | intx operator %(const intx& d) const { |