UVa 1363 Joseph's Problem (等差数列)

发表于 更新于 分类于

题目

题目大意

输入正整数\(n\)和\(k\)(\(1 ≤ n, k ≤ 10^9\)), 计算\(\sum_{i = 1}^{n}k\ mod\ i\)。

题解

被除数固定, 除数逐次加\(1\), 直观上余数也应该有规律: 对于某一个区间\(i, i + 1, i + 2, \cdots , j\), 如果\(k\)除以它们的商的整数部分都相同, 则\(k\)除以它们的余数会是一个等差数列。

这样就就可以在枚举\(i\)的时候把它所在的等差数列之和累加到答案中, 大大降低了时间复杂度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstdio>
#include <algorithm>
long long n, k;
long long ans, i;
int main(int argc, char const *argv[]) {
  while (~scanf("%lld %lld", &n, &k)) {
    ans = std::max(n - k, 0ll) * k, i = 1;
    for (register long long l, r; i * i <= k; ++i) {
      l = k / (i + 1) + 1,
      r = std::min(n, k / i);
      if (l <= r) {
        ans += ((k % r + k % l) * (r - l + 1)) >> 1;
      }
    }
    for (i = std::min(n, k / i); i; --i) ans += k % i;
    printf("%lld\n", ans);
  }
  return 0;
}