平凡的函数 线性筛积性函数

• 2020 年 9 月 4 日
• 筆記
• 数论--线性筛

平凡的函数 线性筛积性函数

题目描述

某一天，你发现了一个神奇的函数\(f(x)\)，它满足很多神奇的性质：

\(1\)、\(f(1)=1\)
\(2\)、\(f(pc)=p⊕c\)
（\(p\) 为质数，\(⊕\)表示异或）。
\(3\)、\(f(ab)=f(a) \times f(b)\)
（\(a\) 与 \(b\)互质）。
你看到这个函数之后十分高兴，于是就想要求出 \(\sum _{i=1}^nf(i)\)。

输入格式

一行一个整数 \(n\)。

输出格式

一行一个整数\(\sum _{i=1}^nf(i)\)。

样例

样例输入 1

6

样例输出 1

16

样例输入 2

233333

样例输出 2

171806766

数据范围与提示

共\(10\) 组测试数据。 对于第\(i\) 组测试数据，满足\(n \leq min \{ 10^i,5 \times 10^7 \}\)

分析

不难发现这是一个积性函数

然后我们用类似于筛欧拉函数的方法去筛它

代码

#include<cstdio>
#include<cmath>
const int maxn=5e7+5;
bool not_pri[maxn];
int pri[maxn],n,f[maxn];
void xxs(){
	for(int i=1;i<=n;i++){
		if(!not_pri[i]){
			pri[++pri[0]]=i;
			f[i]=i^1;
		}
		for(int j=1;j<=pri[0] && pri[j]*i<=n;j++){
			not_pri[i*pri[j]]=1;
			if(i%pri[j]==0){
				int cs=0,now=i*pri[j];
				while(now%pri[j]==0){
					now/=pri[j];
					cs++;
				}
				//根据打表，这样写是线性的
				f[i*pri[j]]=f[now]*(pri[j]^cs);
				break;
			}
			else {
				f[i*pri[j]]=f[i]*f[pri[j]];
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	f[1]=1;
	not_pri[0]=not_pri[1]=1;
	xxs();
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans=ans+f[i];
	}
	printf("%lld\n",ans);
	return 0;
}