@param n `n < 2^32` @param m `1 <= m < 2^32` @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)
| 180 | // @param m `1 <= m < 2^32` |
| 181 | // @return sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64) |
| 182 | unsigned long long floor_sum_unsigned(unsigned long long n, |
| 183 | unsigned long long m, |
| 184 | unsigned long long a, |
| 185 | unsigned long long b) { |
| 186 | unsigned long long ans = 0; |
| 187 | while (true) { |
| 188 | if (a >= m) { |
| 189 | ans += n * (n - 1) / 2 * (a / m); |
| 190 | a %= m; |
| 191 | } |
| 192 | if (b >= m) { |
| 193 | ans += n * (b / m); |
| 194 | b %= m; |
| 195 | } |
| 196 | |
| 197 | unsigned long long y_max = a * n + b; |
| 198 | if (y_max < m) break; |
| 199 | // y_max < m * (n + 1) |
| 200 | // floor(y_max / m) <= n |
| 201 | n = (unsigned long long)(y_max / m); |
| 202 | b = (unsigned long long)(y_max % m); |
| 203 | std::swap(m, a); |
| 204 | } |
| 205 | return ans; |
| 206 | } |
| 207 | |
| 208 | } // namespace internal |
| 209 |