洛谷 P1403 约数研究

P1403 约数研究 - 洛谷

前置知识

1. \(a\) 能整除 \(b\) 用符号表示为 \(b\mid a\)

2. \(1\sim n\) 中约数（即因子）含 \(x\) 的个数 为 \(\left\lfloor\dfrac{n}{x}\right\rfloor\)

证明

对于 \(x\) 作为因子，\(x\) 一定为 \(2x，3x，4x，...，kx\) 的因子，则 \(k=\left\lfloor\dfrac{n}{x}\right\rfloor\)

所以 \(answer=k-1+1=k=\left\lfloor\dfrac{n}{x}\right\rfloor\)

解决该题

假设求\(f(6)\)

1 的约数：1
2 的约数：1，2
3 的约数：1， ，3
4 的约数：1，2， ，4
5 的约数：1， ， ， ，5
6 的约数：1，2，3， ， ，6

正常思路：求每个数的约数个数，再求和

换种思路：求 \(1\sim n\) 中有多少个数约数含 \(i\) ，其中\(i\in [1,n]\)

证明：

\[由题得，要求的值为\sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\sum_{d\mid i}1 \]

\[即\sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\sum_{d=1}^{n}{(d\mid i)} \]

\[交换求和顺序\sum_{i=1}^{n}f(i)=\sum_{d=1}^{n}\sum_{i=1}^{n}{(d\mid i)} \]

\[由前置知识2得 \sum_{i=1}^{n}f(i)=\sum_{d=1}^{n}\left\lfloor\dfrac{n}{d}\right\rfloor \]

Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans += n / i;
        }
        System.out.println(ans);
    }
}