题解 | #因数之和#

B. 因数之和

知识点：调和级数、前缀和

如果一上来就开始打表找规律，那多半是寄了。我们考虑把所有数的因数之和都求出来。

记 表示 的所有因数之和，枚举 ~ 的每个数 ，把 加到所有满足 为 的倍数的 里。

分析一下时间复杂度：

是经典的调和级数，使用积分可求得复杂度为 。

然后再开一个数组 ，如果 ， 就取 ，否则取 。计算数组 的前缀和，就可以快速查询区间 内有多少个数符合条件。

标程

C++

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1000000 + 9;

int a[N];
int s[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 1; i < N; ++i)
        for (int j = i; j < N; j += i)
            a[j] += i;
    for (int i = 1; i < N; ++i)
        s[i] = s[i - 1] + (a[i] >= 2 * i);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        int l, r;
        cin >> l >> r;
        int ans = s[r] - s[l - 1];
        cout << ans << '\n';
    }
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static Kattio io = new Kattio();

    final static int N = 1000000 + 9;
    static int[] a = new int[N];
    static int[] sum = new int[N];
    public static void main(String[] args) {
        for (int i = 1; i < N; ++i) {
            for (int j = i; j < N; j += i) {
                a[j] += i;
            }
        }

        for (int i = 1; i < N; ++i) {
            sum[i] = sum[i - 1] + (a[i] >= 2 * i ? 1 : 0);
        }

        int n = io.nextInt();
        for (int i = 0; i < n; ++i) {
            int l = io.nextInt();
            int r = io.nextInt();
            io.println(sum[r] - sum[l - 1]);
        }

        io.close();
    }
}

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;
    // 标准 IO
    public Kattio() { this(System.in, System.out); }
    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }
    // 在没有其他输入时返回 null
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {}
        return null;
    }
    public int nextInt() { return Integer.parseInt(next()); }
    public double nextDouble() { return Double.parseDouble(next()); }
    public long nextLong() { return Long.parseLong(next()); }
}

Python

N = 1000000 + 9

a = [0] * N
s = [0] * N


for i in range(1, N):
    for j in range(i, N, i):
        a[j] += i

for i in range(1, N):
    s[i] = s[i - 1] + (a[i] >= 2 * i)

n = int(input())
for _ in range(n):
    l, r = map(int, input().split())
    ans = s[r] - s[l - 1]
    print(ans)