2012: 因子和

Time Limit:?2 Sec??Memory Limit:?128 MB
Submit:?38??Solved:?12
[Submit][Status][Web Board]

Description

現(xiàn)有一個(gè)函數(shù)f(n)，表示n的所有因子和。??

例如f(3) = 4,f(6) = 12??

現(xiàn)在有一個(gè)區(qū)間[l,r]??

請(qǐng)你計(jì)算出:??

$$\sum_{i = l} ^ r f(i)$$

Input

多組數(shù)據(jù)(<=10)

每組數(shù)據(jù)包含兩個(gè)整數(shù)l,r(1 <= l <= r <= 1e12)

(r - l <= 1e6)

Output

輸出一個(gè)整數(shù)

Sample Input

101 101

28 28

1 10

Sample Output

102

56

87

解析：設(shè)為i的因子和。

我們先從簡單的開始，我們求1到n的因子和。

以12為例
則 i????1? ?2? ?3? ?4? ?5? ?6? ?7? ?8? ?9? 10? 11? 12
因子? 1? ?1? ?1? ?1? ?1? ?1? ?1? ?1? ?1? ?1? ? 1? ? 1
? ? ? ? ? ? ? ?2? ?3? ?2? ?5? ?2? ?7? ?2? ?9? ?2? ?11? ?2
? ? ? ? ? ? ? ? ? ? ? ? ?4? ? ? ? 3? ? ? ? 4? ? ? ? 5? ? ? ? ? 3?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?6? ? ? ? 8? ? ? ?10? ? ? ? ?6
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 12
則 ans = σ(1)? + σ(2) + ---- + σ(12)
? ?= 12*1 + 6*2 + 4*3 +? 3*4 + 2*5 + 2*6 +? 1*7 + 1*8 + 1*9 + 1*10 + 1*11 + 1*12
? ?=? Σ(1 -> n) (n/i) * i? ? ?注： 這里的/ 是整除的意思
然后我們這樣看
ans = 12*1 + 6*2 + 4*3 + 3*4 + 2*(5+6) + 1*(7+8+9+10+11+12)
則對(duì)于每一個(gè) n/i 都有一個(gè)范圍
n/i 范圍[l, r]? ? ? ? 當(dāng)前n/i 在范圍內(nèi) 對(duì)ans的貢獻(xiàn)是

12[1,1]?12 * 1
6?[2,2]? ?6 * 2
4?[3,3]? ?4 * 3
3 [4,4]? ?3 * 4
2?[5,6]? ?2 * (5 + 6)
1[7,12]? 1 * (7 + 8 + --- + 12)? ? ? 對(duì)于 7+--+8 等差數(shù)列求和 n(a1+an)/2


可以發(fā)現(xiàn) 每一個(gè)l等于上一個(gè)r+1 而r = n/(n/l)? (這里可能不好想-^-^-也就是積性函數(shù)（可看積性函數(shù)的一些函數(shù)）,就是數(shù)論的分塊，我是這么想的，或者你記住，n/i的值是有連續(xù)的區(qū)間的值相等的)
則代碼。。。
(j-i+1)*(i+j)/2相當(dāng)于n(a1+an)/2

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}ull x(ull n) {ull ans=0,j;for(ull i=1;i<=n;i=j+1){j=n/(n/i);ans+=(j-i+1)*(i+j)/2*(n/i);}return ans; } int main() {ull a,b;while(~scanf("%llu%llu",&a,&b)){printf("%llu\n",x(b)-x(a-1));}return 0; }

補(bǔ)充題：求前i個(gè)的因子個(gè)數(shù)的總和；

思路也是相同的

題目鏈接?https://www.nowcoder.com/acm/contest/39/A

主要代碼：

LL X(LL n) {LL l, r;LL ans = 0;for( l = 1; l <= n; l = r+1){r = n/(n/l);ans += n/l * (r - l + 1);}return ans; }

?

總結(jié)

以上是生活随笔為你收集整理的zcmu2012（积性函数---因子和）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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