目錄
- 0 鏈接
- 1 描述
- 2 分析
- 2.1杜教篩
- 2.1.1 莫比烏斯反演
- 2.1.2 迪立克利卷積 g ? f g*f g?f
- 2.1.3 杜教篩
- 2.2 數學模型
- 2.2.1 已知條件
- 2.2.2 結論
- 3 代碼
- 3.1 方法一【468MS】
- 3.1.1 說明
- 3.1.2 代碼
0 鏈接
- HDU 5608 function - http://acm.hdu.edu.cn/showproblem.php?pid=5608
1 描述
- 已 知 N 2 ? 3 N + 2 = ∑ d ∣ N f ( d ) ， 求 ∑ i = 1 n f ( i ) . 已知 N^2-3N+2 = \sum_{d|N}f(d)， 求\sum_{i=1}^{n}f(i). 已知N2?3N+2=∑d∣N?f(d)，求∑i=1n?f(i).
2 分析
2.1杜教篩
-
2.1.1 莫比烏斯反演
N
2
?
3
N
+
2
=
∑
d
∣
N
f
(
d
)
，
根
據
莫
比
烏
斯
反
演
得
：
N^2-3N+2 = \sum_{d|N}f(d)，根據莫比烏斯反演得：
N2?3N+2=d∣N∑?f(d)，根據莫比烏斯反演得：
f
(
n
)
=
∑
d
∣
n
(
d
?
2
)
?
(
d
?
1
)
?
μ
(
n
d
)
f(n)=\sum_{d|n}(d-2)\cdot (d-1)\cdot \mu(\frac{n}{d})
f(n)=d∣n∑?(d?2)?(d?1)?μ(dn?)
-
2.1.2 迪立克利卷積 g ? f g*f g?f
( g ? f ) ( n ) = ∑ d ∣ n g ( d ) ? f ( n d ) = ∑ d ∣ n g ( n d ) ? f ( d ) (g*f)(n) = \sum_{d|n}g(d)\cdot f(\frac{n}{d}) = \sum_{d|n}g(\frac{n}{d})\cdot f(d) (g?f)(n)=d∣n∑?g(d)?f(dn?)=d∣n∑?g(dn?)?f(d)
-
2.1.3 杜教篩
∑
i
=
1
n
(
g
?
f
)
(
i
)
=
∑
i
=
1
n
∑
d
∣
i
g
(
d
)
?
f
(
i
d
)
\sum_{i=1}^{n}(g*f)(i)= \sum_{i=1}^{n}\sum_{d|i}g(d)\cdot f(\frac{i}{d})
i=1∑n?(g?f)(i)=i=1∑n?d∣i∑?g(d)?f(di?)
=
∑
d
=
1
n
(
g
(
d
)
?
∑
i
d
=
1
?
n
d
?
f
(
i
d
)
)
=
∑
d
=
1
n
g
(
d
)
?
S
(
?
n
d
?
)
=\sum_{d=1}^{n}\left(g(d)\cdot \sum_{\frac{i}{d}=1}^{\lfloor\frac{n}{d}\rfloor}f(\frac{i}{d})\right)=\sum_{d=1}^{n}g(d)\cdot S(\lfloor\frac{n}{d}\rfloor)
=d=1∑n????g(d)?di?=1∑?dn???f(di?)???=d=1∑n?g(d)?S(?dn??)
=
g
(
1
)
?
S
(
n
)
+
∑
d
=
2
n
g
(
d
)
?
S
(
?
n
d
?
)
，
式
中
S
(
k
)
=
∑
i
=
1
k
f
(
i
)
=g(1)\cdot S(n)+\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d} \rfloor)，式中S(k)=\sum_{i=1}^{k}f(i)
=g(1)?S(n)+d=2∑n?g(d)?S(?dn??)，式中S(k)=i=1∑k?f(i)
∴
g
(
1
)
?
S
(
n
)
=
∑
i
=
1
n
(
g
?
f
)
(
i
)
?
∑
d
=
2
n
g
(
d
)
?
S
(
?
n
d
?
)
\therefore \quad g(1)\cdot S(n)=\sum_{i=1}^{n}(g*f)(i)-\sum_{d=2}^{n}g(d)\cdot S(\lfloor\frac{n}{d} \rfloor)
∴g(1)?S(n)=i=1∑n?(g?f)(i)?d=2∑n?g(d)?S(?dn??)
2.2 數學模型
-
2.2.1 已知條件
∑
d
∣
N
f
(
d
)
?
1
=
(
f
?
I
)
(
n
)
=
(
I
?
f
)
(
n
)
=
∑
d
∣
N
1
?
f
(
n
d
)
，
式
中
I
(
n
)
=
1
\sum_{d|N}f(d)\cdot 1 = (f*I)(n)=(I*f)(n)=\sum_{d|N}1\cdot f(\frac{n}{d}) ，式中I(n)=1
d∣N∑?f(d)?1=(f?I)(n)=(I?f)(n)=d∣N∑?1?f(dn?)，式中I(n)=1
即
：
N
2
?
3
N
+
2
=
∑
d
∣
N
1
?
f
(
n
d
)
即：N^2-3N+2=\sum_{d|N}1\cdot f(\frac{n}{d})
即：N2?3N+2=d∣N∑?1?f(dn?)
-
2.2.2 結論
S
(
N
)
=
∑
i
=
1
N
(
i
2
?
3
i
+
2
)
?
∑
d
=
2
N
1
?
S
(
?
N
d
?
)
S(N) =\sum_{i =1}^{N}(i^2-3i+2)-\sum_{d=2}^{N}1\cdot S(\lfloor\frac{N}{d} \rfloor)
S(N)=i=1∑N?(i2?3i+2)?d=2∑N?1?S(?dN??)
=
∑
i
=
1
n
(
i
?
2
)
(
i
?
1
)
?
∑
d
=
2
N
S
(
?
N
d
?
)
=\sum_{i =1}^{n}(i-2)(i-1)-\sum_{d=2}^{N}S(\lfloor\frac{N}{d} \rfloor)
=i=1∑n?(i?2)(i?1)?d=2∑N?S(?dN??)
=
n
?
(
n
?
1
)
?
(
n
?
2
)
3
?
∑
d
=
2
N
S
(
?
N
d
?
)
\quad\quad=\frac{n\cdot (n-1)\cdot (n-2)}{3}-\sum_{d=2}^{N}S(\lfloor\frac{N}{d} \rfloor)
=3n?(n?1)?(n?2)??d=2∑N?S(?dN??)
3 代碼
3.1 方法一【468MS】
3.1.1 說明
- 預處理函式pre()
- 根據 f ( n ) = ( n ? 1 ) ( n ? 2 ) ? f ( 1 ) ? … ， n < 1 e 6 f(n)=(n-1)(n-2)-f(1)-…，n < 1e6 f(n)=(n?1)(n?2)?f(1)?…，n<1e6計算f(n)，時間復雜度 O ( n ? log ? ( n ) ) O(n\cdot \log(n)) O(n?log(n))
- 根據f(n)求 ∑ i = 1 n f ( i ) \sum_{i=1}^{n}f(i) ∑i=1n?f(i)
- 求前綴和函式get_sum()
- 如果n>1e6，則杜教篩；否則查表
3.1.2 代碼
// hdu 5608 function
#include<bits/stdc++.h>
using namespace std;
#define inv 333333336
#define mxn 1000010
#define mod 1000000007
int n, t, ans[mxn];
map<int,int> q;
void pre(){// 計算f(n)及其前綴和
for(int i = 1; i < mxn; ++i)
ans[i] = 1LL*(i-2)*(i-1)%mod;
for(int i = 1; i < mxn; ++i){// 計算f(n)
for(int j = 2*i; j < mxn; j+=i){
ans[j] -= ans[i];
if(ans[j] < 0) ans[j] += mod;
}
}
for(int i = 2; i < mxn; ++i){// f(n)的前綴和
ans[i] += ans[i-1];
if(ans[i] >= mod) ans[i] -= mod;
}
}
int get_sum(int x){
if(x < mxn) return ans[x];
if(q.count(x)) return q[x];
int res = 1LL*inv*x%mod*(x-1)%mod*(x-2)%mod;
for(int i = 2, j; i <= x; i = j+1){// 整除分塊
j = x/(x/i);
res -= 1LL*(j-i+1)*get_sum(x/i)%mod;
if(res < 0) res += mod;
}
return q[x] = res;
}
int main(){
pre();
scanf("%d", &t);
while(t--){
scanf("%d", &n);
printf("%d\n", get_sum(n));
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/287675.html
標籤：其他
上一篇：Spark SQL資料型別