HDU 6134 Battlestation Operational(2017 Multi-University Training Contest - Team 8)

HDU 6134 Battlestation Operational

题目大意:求$f(n)=\sum_{i=1}^n\sum_{j=1}^i \lceil \frac{i}{j} \rceil [(i,j)=1]$ 。

莫比乌斯反演

首先,有一个据说很著名的等式:
$$
\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor =\sum_{i=1}^n \sigma(i)
$$
其中$\sigma(n)$ 为$n$ 的因数个数。这个等式可以由筛法证明(见代码)。

然后我们来化简下题目中所要求的函数$f(n)$ 。
$$
f(n)=\sum_{i=1}^n \sum_{j=1}^i \lceil \frac{i}{j} \rceil [(i,j)=1]\\
=\sum_{i=1}^n(\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor[(i,j)=1] +\varphi(i)-1)\\
=\sum_{i=1}^n\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor[(i,j)=1] +\sum_{i=1}^n\varphi(i)-n\\
$$
设$g(n)=\sum_{i=1}^n\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor[(i,j)=1],i=k_1d,j=k_2d$ ,则有
$$
g(n)=\sum_{i=1}^n\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor[(i,j)=1]\\
=\sum_{i=1}^n\sum_{j=1}^i \lfloor \frac{i}{j} \rfloor \sum_{d|(i,j)}u(d)\\
=\sum_{d=1}^nu(d)\sum_{k_1=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{k_2=1}^{k_1}\lfloor \frac{k_1}{k_2} \rfloor\\
=\sum_{d=1}^nu(d)\sum_{k_1=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{k_2=1}^{k_1}\sigma(k_2)
$$
$h(n)=\sum_{i=1}^n\sum_{j=1}^{i}\sigma(j)$ 预处理的复杂度为$O(nlogn)$ 。

于是$f(n)=\sum_{d=1}^nu(d)h(\lfloor \frac{n}{d} \rfloor)+\sum_{i=1}^n\varphi(i)-n$ 可以在$O(\sqrt{n})$ 的复杂度求出。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1000001;
const ll p=1e9+7;
ll d[N],h[N],sumd,n;
ll prime[N],vis[N]={1,1},k,phi[N]={0,1},pphi[N],mu[N]={0,1},pmu[N];
ll Max(ll a,ll b){
return a>b?a:b;
}
void init(){
for(int i=2;i<N;++i){
if(!vis[i]){
prime[k++]=i;
phi[i]=i-1;
mu[i]=-1;
}
for(int j=0;j<k&&prime[j]*i<N;++j){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
phi[i*prime[j]]=phi[i]*prime[j];
break;
}else{
mu[i*prime[j]]=-mu[i];
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
for(int i=1;i<N;++i)
for(int j=i;j<N;j+=i)
d[j]++;//预处理\sigma(n)
for(int i=1;i<N;++i){
sumd=(sumd+d[i])%p;
h[i]=(h[i-1]+sumd)%p;
}
for(int i=1;i<N;++i){
pphi[i]=(pphi[i-1]+phi[i])%p;
pmu[i]=pmu[i-1]+mu[i];
}
}
ll solve(ll n){
ll ans=((pphi[n]-n)%p+p)%p;
for(ll d=1;d<=n;){
ll pd=Max(d,n/(n/d));
ans+=(pmu[pd]-pmu[d-1])*h[n/d]%p;
ans=(ans+p)%p;
d=pd+1;
}
return ans;
}
int main(void){
init();
while(~scanf("%I64d",&n))
printf("%I64d\n",solve(n));
}

Comentarios

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×