題干：
?

給個(gè)n，求1到n的所有數(shù)的約數(shù)個(gè)數(shù)的和~

輸入描述:

第一行一個(gè)正整數(shù)n

輸出描述:

輸出一個(gè)整數(shù)，表示答案

示例1

輸入

復(fù)制

3

輸出

復(fù)制

5

說明

樣例解釋： 1有1個(gè)約數(shù)1 2有2個(gè)約數(shù)1,2 3有2個(gè)約數(shù)1,3

備注:

n <= 100000000

解題報(bào)告：

? ?看到數(shù)據(jù)范圍，nlogn打表肯定是不行的，但是因?yàn)榍蟮氖撬袛?shù)的約數(shù)個(gè)數(shù)和，考慮每個(gè)數(shù)約數(shù)k，1~n這些數(shù)的約數(shù)中有k的數(shù)是n/k個(gè),所以k給答案加上n/k。

AC代碼：

#include<iostream> using namespace std; int main() {int n,i,s=0;cin>>n;for(i=1;i<=n;i++)s+=n/i;cout<<s;return 0; }

法二：

也就是，所以有這個(gè)公式，至于為什么可以O(shè)(sqrt(n))求解，

有很多都是一樣的 對(duì)于這些一樣的數(shù)我們每次算一次 似乎很浪費(fèi)時(shí)間

所以我們每次i跳到這樣的j上 對(duì)于中間一樣的數(shù)一次性算掉

這樣的復(fù)雜度又是多少呢?打表測試一下就好了 復(fù)雜度O(2*sqrt(n)?).

AC代碼：

#include <bits/stdc++.h> using namespace std; long long ans; int main() {int n;scanf("%d", &n);for (int i = 1, j; i <= n; i = j + 1) {j = min(n, n / (n / i));ans += (long long)(j - i + 1) * (n / i);}printf("%lld\n", ans);return 0; }

對(duì)于O(sqrt(n))的算法還有另一種解釋：

https://blog.csdn.net/zzcblogs/article/details/78816533

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 练习】约数个数的和（数论，数学）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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