題目要求

P1403題目鏈接

---

分析

這是一個(gè)數(shù)論題，這種數(shù)學(xué)題你要是盲目開暴力可能會很菜或者想不出思路，這里講講比較666的思路。

$O(n)$復(fù)雜度解法

可以用純數(shù)學(xué)證明一種時(shí)間復(fù)雜度為$O(\sqrt{n})$的算法：

$\sum _{i=1}^n\sigma (i)=\sum _{i=1}^n\sum _{d|i}1=\sum _{i=1}^n\sum _{d=1}^n[d|i]=\sum _{d=1}^n\sum _{i=1}^n[d|i]=\sum _{d=1}^n?\frac{d}{i}?$

而對于該算法具體實(shí)現(xiàn)的解讀可以推薦看這篇$dalao$的文章

---

我可以給大家看一下我是怎么編輯公式的，這個(gè)對大家也很有用的：

---

Latex語法補(bǔ)充

向上取整：$?x?$

$\lfloor x \rfloor$

向下取整：$?x?$

$\lceil x \rceil$

分?jǐn)?shù)：$\frac{x}{y}$

$\frac{x}{y}$

積分號：$\sum _{i=1}^n\sigma (i)$

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

注意，想要上下限不在右側(cè)而是上下側(cè)，需要加上\limits

$Want$ $To$ $Know$ $More$ $?$ $Look$ $At$ $Here$ $!$

---

實(shí)在看不懂？沒關(guān)系（除非你是搞競賽的），你看得懂代碼就行了！

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 <= num; i = j+1) {j = num/(num/i);result += (num/i)*(j-i+1);}System.out.println(result);} }

總結(jié)

以上是生活随笔為你收集整理的约数研究问题的算法优化和推导证明（洛谷P1403题题解，Java语言描述，含Latex公式编辑知识）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。