• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

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

开发技术 开发技术 4周前 (09-04) 27次浏览

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

题目描述

某一天,你发现了一个神奇的函数(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("%lldn",ans);
	return 0;
}


喜欢 (0)