今天一下午都在研究約數的各種性質。。。
求約數個數的和可以用線性篩的方式，線性求解的方式，這應該是最快的
[數論]線性篩——約數個數與約數和
除此之外還有代碼更簡便方法：
對應的例題

方法一：

#include <iostream> using namespace std; int OneToNumGcdCount(int num) {int ans = 0;for (int i = 1; i <= num; i++) {ans += num / i;}return ans; } int main() {int t1, t2, t;cin >> t1 >> t2 ;t = OneToNumGcdCount(t2)- OneToNumGcdCount(t1-1);cout << t;return 0; }

方法二：

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m; ll get(ll n){long long ans=0, t=sqrt((double)(n));for(int i=1; i<=t; i++)ans += n/i;ans = ans*2-t*t;return ans; } int main(){scanf("%lld%lld",&n,&m);cout<<get(m)-get(n-1)<<endl;return 0; }

代碼二的時間復雜度更低，個人感覺代碼二應該是代碼一的優化版本

總結

以上是生活随笔為你收集整理的求约数个数的和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。