Description：

已知一个函数：

$f(1)=1$ ， $f(p^c)=p\text{ xor }c$ ，半积性。

求： $$ \sum_{i=1}^nf(i) $$ $1\leqslant n\leqslant10^{10}$

Solution：

首先除了 $2$ 之外所有的质数都是奇数，因此 $f(p)=p\text{ xor }1=p-1$ ，然后由于在刚开始计算 $g$ 的时候要把所有的数都当成质数来计算也就是说： $$ g(n,j)=\sum_{i=2}^nf(i)=\sum_{i=2}^n(i-1)=\sum_{i=2}^ni-\sum_{i=2}^n1 $$ 因此我们设： $$ g(n,j)=\sum_{i=2}^n[i\ is\ prime]i $$ 要同时求一个 $pc(i)$ ： $$ pc(i)=\sum_{i=2}^n[i\ is\ prime]1 $$ 然后 $2$ 要特判。

然后就是一个 $\min\_25$ 筛的模板了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll n;

#define MAXN 1000010

int N;

#define MOD 1000000007

#define INV2 500000004

int prime[MAXN],tot = 0;

int ps[MAXN];

bool isprime[MAXN];

void sieve()

{

	for(int i = 2;i <= N;++i)isprime[i] = true;

	for(int i = 2;i <= N;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			ps[tot] = (ps[tot - 1] + i) % MOD;

		}

		for(int j = 1;j <= tot && i * prime[j] <= N;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)break;

		}

	}

	return;

}

ll w[MAXN],m = 0;

int id1[MAXN],id2[MAXN];

inline int id(ll k){return (k <= N ? id1[k] : id2[n / k]);}

int pc[MAXN];

int g[MAXN];

int S(ll n,int j)

{//cout << n << " " << j << endl;

	if(n <= 1 || prime[j] > n)return 0;

	int k = id(n);

	int res = (((g[k] - pc[k] + MOD) % MOD - ps[j - 1] + MOD) % MOD + j - 1) % MOD;

	if(j == 1)res = (res + 2) % MOD;

	for(int i = j;i <= tot && 1ll * prime[i] * prime[i] <= n;++i)

	{

		ll p1 = prime[i],p2 = 1ll * prime[i] * prime[i];

		for(int e = 1;p2 <= n;++e,p1 = p2,p2 *= prime[i])

		{

			res = ((res + 1ll * S(n / p1,i + 1) * (prime[i] ^ e) % MOD) % MOD + (prime[i] ^ (e + 1))) % MOD;

		}

	}

	return res;

}

int main()

{

	cin >> n;

	N = sqrt(n);

	sieve();

	for(ll l = 1,r;l <= n;l = r + 1)

	{

		r = n / (n / l);

		w[++m] = n / l;

		if(w[m] <= N)id1[w[m]] = m;

		else id2[n / w[m]] = m;

		pc[m] = (w[m] - 1) % MOD;

		g[m] = ((w[m] + 2) % MOD) * ((w[m] - 1) % MOD) % MOD * INV2 % MOD; 

	}

	for(int j = 1;j <= tot;++j)

	{

		for(int i = 1;i <= m && 1ll * prime[j] * prime[j] <= w[i];++i)

		{

			int k = id(w[i] / prime[j]);

			pc[i] = ((pc[i] - pc[k] + MOD) % MOD + j - 1) % MOD;

			g[i] = (g[i] - 1ll * prime[j] * ((g[k] - ps[j - 1] + MOD) % MOD) % MOD + MOD) % MOD;

		}

	}

	cout << (S(n,1) + 1) % MOD << endl;

	return 0;

}