题目概述

定义积性函数 $f(n)$ 满足 $f(p^k)=p\ xor\ k$ ，求 $\sum_{i=1}^{n}f(i)$ 。

解题报告

不难发现除了 $f(2)=3$ 之外，$f(p)=p-1$ 。为了方便我们假装 $f(2)=1$ ，在最后加上 $2$ 即可。

由于给出的是 $f(p^k)$ 的计算方法，所以考虑Min_25筛，但是 $f(p)=p-1$ 对应的 $h(n)=n-1$ 不是完全积性函数，我们可以将其拆成 $f_1(p)=p,f_2(p)=1$ ，这样就可以Min_25筛了。

示例程序

#include<cmath>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxs=200000,MOD=1e9+7,INV2=MOD+1>>1;

int S,p[maxs+5],sp[maxs+5];bool pri[maxs+5];LL n;
int m,ID[2][maxs+5],g[maxs+5],h[maxs+5];LL a[maxs+5];

inline void Make(int n){
    for (int i=2;i<=n;i++){
        if (!pri[i]) p[++p[0]]=i,sp[p[0]]=(sp[p[0]-1]+i)%MOD;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=n;j++)
            {pri[t]=true;if (!(i%p[j])) break;}
    }
}
int Sum(LL a,int b){
    if (a<=1||p[b]>a) return 0;int k=(a<=S?ID[0][a]:ID[1][n/a]);
    int ans=((LL)g[k]+MOD-h[k]+b-1+MOD-sp[b-1])%MOD;
    for (int i=b;i<=p[0]&&(LL)p[i]*p[i]<=a;i++){
        LL A=p[i],B=A*A;
        for (int j=1;B<=a;A=B,B*=p[i],j++)
            ans=(ans+(LL)(p[i]^j)*Sum(a/A,i+1)%MOD+(p[i]^j+1))%MOD;
    }if (b==1) ans=(ans+2)%MOD;return ans;
}
inline int Min25(LL x){
    n=x;S=sqrt(n);m=0;
    for (LL l=1,r;l<=n;l=r+1){
        r=n/(n/l);a[++m]=n/l;g[m]=((a[m]+2)%MOD)*((a[m]-1)%MOD)%MOD*INV2%MOD;h[m]=(a[m]-1)%MOD;
        a[m]<=S?ID[0][a[m]]=m:ID[1][n/a[m]]=m;
    }
    for (int j=1;j<=p[0]&&p[j]<=S;j++)
        for (int i=1;i<=m&&(LL)p[j]*p[j]<=a[i];i++){
            int k=(a[i]/p[j]<=S?ID[0][a[i]/p[j]]:ID[1][n/(a[i]/p[j])]);
            g[i]=(g[i]+MOD-(LL)p[j]*(g[k]+MOD-sp[j-1])%MOD)%MOD;h[i]=(h[i]+MOD-h[k]+j-1)%MOD;
        }
    return (Sum(n,1)+1)%MOD;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%lld",&n);Make(maxs);printf("%d\n",Min25(n));return 0;
}