"约数研究"问题的算法优化和推导证明（洛谷P1403题题解，Java语言描述，含Latex公式编辑知识）

题目要求

P1403题目链接

分析

这是一个数论题，这种数学题你要是盲目开暴力可能会很菜或者想不出思路，这里讲讲比较666的思路。

O ( n ) O(n) O(n)复杂度解法

可以用纯数学证明一种时间复杂度为 O ( n ) O(\sqrt{n}) O(n ​)的算法：

∑ i = 1 n σ ( i ) = ∑ i = 1 n ∑ d ∣ i 1 = ∑ i = 1 n ∑ d = 1 n [ d ∣ i ] = ∑ d = 1 n ∑ i = 1 n [ d ∣ i ] = ∑ d = 1 n ⌊ d i ⌋ \sum\limits_{i=1}^{n}\sigma(i) = \sum\limits_{i=1}^{n}\sum\limits_{d|i}1 = \sum\limits_{i=1}^{n}\sum\limits_{d=1}^{n}{[d|i]} = \sum\limits_{d=1}^{n}\sum\limits_{i=1}^{n}{[d|i]} = \sum\limits_{d=1}^{n}{\lfloor{\frac{d}{i}}\rfloor} i=1∑n​σ(i)=i=1∑n​d∣i∑​1=i=1∑n​d=1∑n​[d∣i]=d=1∑n​i=1∑n​[d∣i]=d=1∑n​⌊id​⌋

而对于该算法具体实现的解读可以推荐看这篇 d a l a o dalao dalao的文章

我可以给大家看一下我是怎么编辑公式的，这个对大家也很有用的：

Latex语法补充

向上取整： ⌊ x ⌋ \lfloor x \rfloor ⌊x⌋

$\lfloor x \rfloor$

向下取整： ⌈ x ⌉ \lceil x \rceil ⌈x⌉

$\lceil x \rceil$

分数： x y \frac{x}{y} yx​

$\frac{x}{y}$

积分号： ∑ i = 1 n σ ( i ) \sum\limits_{i=1}^{n}\sigma(i) i=1∑n​σ(i)

$\sum\limits_{i=1}^{n}\sigma(i)$

注意，想要上下限不在右侧而是上下侧，需要加上\limits

W a n t Want Want T o To To K n o w Know Know M o r e More More ? ? ? L o o k Look Look A t At At H e r e Here Here ! ! !

实在看不懂？没关系（除非你是搞竞赛的），你看得懂代码就行了！

AC代码（Java语言描述）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        scanner.close();
        int result = 0;
        for(int i = 1, j; i