「Project Euler 512」Sums of totients of powers

Problem

Description

定义 f(n)

f(n)=\left(\sum_{i=1}^{n}\varphi(n^{i})\right)\bmod{(n + 1)}

其中 \varphi(n) Euler's totient Function
定义 g(n)

g(n)=\sum_{i=1}^{n}f(i)

g\left(100\right)=2007
g\left(5\times 10^{8}\right)

Solution

Analysis

分析 f(n) ,可以发现

\begin{aligned} \varphi\left(n^{k}\right)=&\prod_{i=1}^{\omega(n)}\varphi\left(p_{i}^{k\nu_{p_{i}}(n)}\right)\\ =&\prod_{i=1}^{\omega(n)}p^{\left(k-1\right)\nu_{p_{i}}(n)}\varphi\left(p_{i}^{\nu_{p_{i}}(n)}\right)\\ =&n^{k-1}\prod_{i=1}^{\omega(n)}\varphi\left(p_{i}^{\nu_{p_{i}}(n)}\right)\\ =&n^{k-1}\varphi(n) \end{aligned}

\begin{aligned} f(n)=&\left(\sum_{i=1}^{n}\varphi(n^{i})\right)\pmod{n+1}\\ =&\left(\sum_{i=1}^{n}n^{i-1}\varphi(n)\right)\pmod{n+1}\\ =&\left(\varphi(n)\sum_{i=1}^{n}n^{i-1}\right)\pmod{n+1} \end{aligned}

注意到

n\equiv -1\pmod{n+1}

\begin{aligned} f(n)&=\left(\varphi(n)\sum_{i=1}^{n}(-1)^{i-1}\right)\pmod{n+1}\\ &=\begin{cases}0&n\equiv 0\pmod{2}\\\varphi(n)&n\equiv 1\pmod{2}\end{cases} \end{aligned}

线性筛计算即可。
时间复杂度 O(n)
等等...空间复杂度?

\frac{5\cdot 10^{8}\cdot\left(4+1\right)}{2^{20}}\approx 2384.18579\left(MegaByte\right)

根本跑不起来...直接 RE 了
优化方法?

qwq

可以发现偶数对于答案完全没有贡献,并且偶数对于需要计算的 \varphi 值也是没有贡献的(奇数不可能含有一个偶因子)。
故可以压缩数组,将 2n+1 对应的值存在数组中下标为 n 处即可。

时间复杂度 O(n)

Code

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
#include<cstdio>

using i64=long long;
#define Maxn 250000001
#define Maxcnt 27000000

bool notPrime[Maxn];
int phi[Maxn];
int Prime[Maxcnt];
int cnt;
i64 Ans=1;

void Sieve(const int&Limit){
for(int i=3;i<=Limit;i+=2){
int ci=i>>1;
if(!notPrime[ci])
Prime[++cnt]=i,phi[ci]=i-1;
Ans+=phi[ci];
for(int j=1,phii=phi[ci];j<=cnt;++j){
int to=i*Prime[j];
if(Limit<to)
break;
int ct=to>>1;
notPrime[ct]=true;
if(i%Prime[j])
phi[ct]=phii*(Prime[j]-1);
else{
phi[ct]=phii*Prime[j];
break;
}
}
}
}

int main(){
const int n=500000000;
Sieve(n);
return(printf("%lld",Ans),0);
}