​ 对一切正整数$x$有确切值的函数$f(x)$ ，只要其在全体正整数上的函数值不全为零，就称为一个数论函数。

定义

• 设$f(x)$ 为一个数论函数，若对于每一对互质的正整数$a$ ，$b$ 都满足$f(ab)=f(a)f(b)$ ，则$f(x)$ 是积性函数。
• 设$f(x)$ 为一个数论函数，若对于每一对正整数$a$ ，$b$ 都满足$f(ab)=f(a)f(b)$ ，则$f(x)$ 是完全积性函数。

线性筛

线性筛可以以$O(n)$的复杂度求得$1 \sim n$的所有素数及各个数的最小素因子：

int prime[N],cnt;
bool isnotprime[N]={1,1};
void sieve(int n){
  for(int i=2;i<=n;++i){
    if(!isnotprime[i])prime[cnt++]=i;
    for(int j=0;j<cnt&&i*prime[j]<=n;++j){
      isnotprime[i*prime[j]]=1;
      if(i%prime[j]==0)break;
    }
  }
}

利用这些信息，可以以递推的方式求得前$n$ 项积性函数值。

例题

POJ 2478 Farey Sequence

题目大意：求$\sum_{i=2}^n \varphi(i)$。

代码如下：

#include <cstdio>
#define N 1000005
using namespace std;
typedef long long ll;
ll var[N],pre[N],prime[N],k;
bool vis[N]={1,1};
void init(){
    for(int i=2;i<=1000000;++i){
        if(!vis[i]){
            prime[k++]=i;
            var[i]=i-1;
        }
        for(int j=0;j<k&&prime[j]*i<=1000000;++j){
            vis[prime[j]*i]=1;
            if(i%prime[j]==0){
                var[prime[j]*i]=var[i]*prime[j];
                break;
            }
            var[prime[j]*i]=var[i]*var[prime[j]];
        }
    }
    for(int i=1;i<=1000000;++i)
        pre[i]=pre[i-1]+var[i];
}
int main(void){
    init();
    int n;
    while(scanf("%d",&n)){
        if(n==0)break;
        printf("%lld\n",pre[n]);
    }
}