LOJ6053 简单的函数

LOJ6053 简单的函数

题目大意

有一个函数$f(x)$满足以下性质

• $f(1)=1$
• $f(p^c)=p\oplus c$$p$为质数$\oplus$表示异或
• $f(ab)=f(a)f(b)$$a$与$b$互质

求$\sum _{i=1}^{n}f(i)$对$(10^9+7)$取模的结果其中$1\le n\le 10^{10}$。

题解

前置知识min25筛

观察函数$f(x)$$f(x)$在质数和质数的幂的位置比较好求我们考虑使用min25筛。

当$x$为奇质数时$f(x)=x\oplus 1=x-1$。当$x$为偶质数时$f(x)=x\oplus 1=x+1$。令$p(x)=x-1$用$p$函数代替$f$函数然后将$p$函数分为$f_1(x)=x$和$f_2(x)=1$两个完全积性函数来求min25筛中的$g$函数最后再用$f$函数的性质来求min25筛中的$S$函数。对于$p$和$f$在$x=2$处的差在最后加上即可。

为什么可以这样呢由函数$S(n,i)$的递推式$f(2)$的值改变只会影响$S$的递推式中含有$g$函数的部分。因为答案为$S(n,0)+1$而只有$i=0$时才会涉及到$f(2)$的值$i\ne 0$时两个$g$函数相减将$f(2)$的部分抵消了所以将$f$改为$p$在求答案的情况下只会影响一次也就是答案减少了$f(2)-g(2)=3-1=2$在最后加上即可。

min25筛中函数$S$的递推式

$$S(n,i)=g(n,|pr(n)|)-g(p{r}_i,|pr(n)|)+\sum _{j>i}\sum _{p{r}_j^k\le n}f(p{r}_j^k)\times (S(\lfloor \frac{n}{p{r}_j^k}\rfloor ,j)+[k>1])$$

code

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
const long long mod=1000000007;
int p1,vt,z[N+5],pr[N+5];
long long n,x,v[N+5],f[2][N+5],s1[N+5],s2[N+5],g1[N+5],g2[N+5];
void dd(){
	for(int i=2;i<=N;i++){
		if(!z[i]){
			pr[++p1]=i;
			s1[p1]=(s1[p1-1]+i)%mod;
			s2[p1]=p1;
		}
		for(int j=1;j<=p1&&i*pr[j]<=N;j++){
			z[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}
}
void init(){
	x=sqrt(n)+1;
	dd();
	for(long long l=1,r;l<=n;l=r+1){
		r=n/(n/l);
		v[++vt]=n/l;
		if(n/l<=x) f[0][n/l]=vt;
		else f[1][l]=vt;
		long long t=(n/l)%mod;
		g1[vt]=(t*(t+1)/2%mod-1+mod)%mod;
		g2[vt]=(t-1+mod)%mod;
	}
	long long w;
	for(int i=1;i<=p1;i++){
		w=1ll*pr[i]*pr[i];
		long long t;
		for(int j=1;j<=vt&&w<=v[j];j++){
			t=v[j]/pr[i];
			if(t<=x) t=f[0][t];
			else t=f[1][n/t];
			g1[j]=(g1[j]-1ll*pr[i]*(g1[t]-s1[i-1])%mod+mod)%mod;
			g2[j]=(g2[j]-1ll*(g2[t]-s2[i-1])%mod+mod)%mod;
		}
	}
	
}
long long S(long long p,int q){
	if(pr[q]>=p) return 0;
	long long td=(p<=x?f[0][p]:f[1][n/p]);
	long long re=((g1[td]-g2[td]-s1[q]+s2[q])%mod+mod)%mod;
	for(int j=q+1;j<=p1;j++){
		if(1ll*pr[j]*pr[j]>p) break;
		for(long long o=1,pq=pr[j],t;pq<=p;++o,pq=pq*pr[j]){
			t=pq%mod;
			re=(re+1ll*(pr[j]^o)%mod*(S(p/pq,j)%mod+(o>1))%mod)%mod;
		}
	}
	return re;
}
int main()
{
	scanf("%lld",&n);
	init();
	if(n==1) printf("1");
	else printf("%lld\n",(S(n,0)+3)%mod);
	return 0;
}