BISHI42 余数求和

在这里插入图片描述

求解思路

由于对任意正整数$k, i$，有$k \mod i = k - i \times \lfloor \frac{k}{i} \rfloor$

$$\sum_{i=1}^n (k \mod i) = \sum_{i=1}^n \left( k - i \times \lfloor \frac{k}{i} \rfloor \right) = n \times k - \sum_{i=1}^{\min(n,k)} \left( i \times \lfloor \frac{k}{i} \rfloor \right)$$

求解代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        String[] str = br.readLine().split("\\s+");

        long n = Long.parseLong(str[0]);
        long k = Long.parseLong(str[1]);

        long total = n * k; // 原表达式的第一部分
        long m = Math.min(n, k); // 只需要计算到min(n,k)
        long i = 1;

        while (i <= m) {
            long v = k / i;
            long j = Math.min(k / v, m); // 当前块的右边界
            // 计算i到j的和：(i+j)*(j-i+1)/2，再乘以v
            total -= v * (i + j) * (j - i + 1) / 2;
            i = j + 1; // 跳到下一个块
        }
        out.println(total);
        out.flush();
        out.close();
        br.close();

    }