loj #6053 简单的函数 min_25筛

(color{#0066ff}{ 题目描述 })

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

1. (f(1)=1)
2. (f(p^c)=p oplus c) （(p) 为质数，(oplus) 表示异或）。
3. (f(ab)=f(a)f(b)) （(a) 与 (b) 互质）。

你看到这个函数之后十分高兴，于是就想要求出 (sumlimits_{i=1}^n f(i))。

由于这个数比较大，你只需要输出 (sumlimits_{i=1}^n f(i) mod (10^9+7))

(color{#0066ff}{输入格式})

一行一个整数 (n)。

(color{#0066ff}{输出格式})

一行一个整数 (sumlimits_{i=1}^n f(i) mod 1000000007)。

(color{#0066ff}{输入样例})

6
    
233333
    
9876543210

(color{#0066ff}{输出样例})

16
  
179004642
  
895670833

(color{#0066ff}{数据范围与提示})

对于(30\%)的数据，(n leq 100)。

对于(60\%)的数据，(n leq 10^6)。

对于(100\%)的数据，(1 leq n leq 10^{10})。

(color{#0066ff}{ 题解 })

min_25筛，我们先找到(f(p))

不难发现(f(p))=(p oplus 1)，

对于除了2以外的质数(f(p)=p-1,f(2)=3)

可以把2当成其它来算，最后+2就行了

还是项(varphi)一样拆项，注意贡献的统计，(f(p^c)=poplus c)

#include<bits/stdc++.h>
#define LL  long long
LL in() {
	char ch; LL x = 0, f = 1;
	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
	return x * f;
}
const int maxn = 2e6 + 100;
const int mod = 1e9+7;
LL g0[maxn], g1[maxn], a[maxn];
LL n, m, sqt;
LL pri[maxn], tot;
int getid(LL x) { return x <= sqt? x : m - n / x + 1; }
LL getans(LL a, int b) {
	if(a < pri[b]) return 0;
	LL ans = (((g1[getid(a)] - g1[getid(pri[b - 1])]) % mod) - (g0[getid(a)] - g0[getid(pri[b - 1])]) % mod) % mod ;
	for(int i = b; i <= tot && (LL)pri[i] * pri[i] <= a; i++)
		for(LL x = pri[i], f = 1; x * pri[i] <= a; x *= pri[i], f++)
			(ans += (getans(a / x, i + 1) * (pri[i] ^ f) % mod) + (pri[i] ^ (f + 1)) ) %= mod;
	return ans;
}
signed main() {
	sqt = sqrt(n = in());
	for(LL i = 1; i <= n; i = a[m] + 1)
		a[++m] = n / (n / i), g0[m] = ((a[m] % mod) - 1) , g1[m] = (((a[m] % mod) * ((a[m] % mod) + 1)) / 2 - 1) ;
	for(LL i = 2; i <= sqt; i++) {
		if(g0[i] != g0[i - 1]) {
			pri[++tot] = i;
			LL sqr = i * i;
			for(int j = m; a[j] >= sqr; j--) {
				int id = getid(a[j] / i);
				(g0[j] -= g0[id] - g0[i - 1]) %= mod;
				(g1[j] -= i * (g1[id] - g1[i - 1]) % mod) %= mod;
			}
		}
	}
	printf("%lld
", ((getans(n, 1) + 1 + (n > 1) * 2)) % mod);
	return 0;
}