【题解】#loj6053 简单的函数

给定函数 $f(x)$ 满足:

求 $\sum f(x)$, $n\leq 10^{10}$

单独拿出一道题来整理一下,也算是理一下用 Min_25 解题的一点思路吧。

嗯,首先思考 Min_25 筛本质上需要做什么:

1、对于每个 $x = \lfloor \frac{n}{y}\rfloor$ ,这样不同的 $x$ 共有 $O(\sqrt n)$ 个,需要快速得到

的值。

2、需要根据递推式求出 $g$ 来,同时由于空间不够,而我们其实只需要知道 $g(x,j)$ 在所有 $x = \lfloor \frac{n}{y}\rfloor$ 处的取值就好,所以考虑用两个 $\sqrt n$ 的标号来存。

3、在 $\rm S$ 中,分工很明确,for 之前求的是所有质数处的 $f$ 和,然而由于直接算 $f$ 求出的是 $1\sim n$ 的质数处的 $f$ 和,我们需要的是 $j+ 1\sim n$ 的,所以把 $1\sim j$ 的减去;对于合数,我们枚举每个 $\geq j+1$ 的质数,然后 $\log$ 次向上计算:

直观上可以感觉出有一个很大的上界 $n$,即

。。。然而似乎并没有用,因为线性筛也是这个复杂度233

然后说题,考虑质数处的取值:

然后就可以维护一个 $n$ 一个 $1$,质数次幂就是 $f(p^c)=p\oplus c$ 易求,最后再加上 $2$ 处多减去的 $2$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
LL n ;
LL val[N] ;
LL g[N], h[N] ;
int s, tot, cnt ;
int chk[N], pr[N] ;
LL id1[N], id2[N], sp[N] ;
const int P = 1000000007 ;
const LL Inv2 = 500000004 ;

void sieve(int m){
chk[0] = chk[1] = 1 ;
for (int i = 2 ; i <= m ; ++ i){
if (!chk[i])
pr[++ cnt] = i,
sp[cnt] = (sp[cnt - 1] + i) % P ;
for (int j = 1 ; j <= cnt ; ++ j){
if (i * pr[j] > m) break ;
chk[i * pr[j]] = 1 ;
if (i % pr[j] == 0) break ;
}
}
}
LL S(LL p, int q){
if (pr[q] >= p) return 0 ;
LL id = p <= s ? id1[p] : id2[n / p] ;
LL ans = ((g[id] - h[id] - sp[q] + q) % P + P) % P ;
if (!q) ans += 2 ;
// cout << ans << " " << p << " " << q << endl ;
for (int k = q + 1 ; k <= cnt ; ++ k){
if (1ll * pr[k] * pr[k] > p)
break ; LL m = pr[k], t = pr[k] ; int o ;
for (o = 1 ; m <= p ; ++ o, m *= t)
ans = (ans + 1ll * (pr[k] ^ o) * (S(p / m, k) + (o > 1)) % P) % P ;
}
return ans ;
}
int main(){
cin >> n ; s = sqrt(n) ;
sieve(s) ; LL l, r, w, t ;
if (n == 1) return puts("1"), 0 ;
for (l = 1 ; l <= n ; l = r + 1){
t = n / l ; r = n / t ;
val[++ tot] = t ; h[tot] = ((t - 1) % P + P) % P ;
g[tot] = ((t % P * (t % P + 1) % P * Inv2 % P - 1) % P + P) % P ;
if (t <= s) id1[t] = tot ; else id2[l] = tot ;
}
for (int i = 1 ; i <= cnt ; ++ i){
LL nowp = 1ll * pr[i] * pr[i], w, id ;
if (nowp > n) break ;
for (int j = 1 ; j <= tot && val[j] >= nowp ; ++ j){
w = val[j] / pr[i] ;
id = (w <= s) ? id1[w] : id2[n / w] ;
(h[j] -= h[id] - (i - 1)) %= P ;
(g[j] -= 1ll * pr[i] * (g[id] - sp[i - 1]) % P) %= P ;
}
}

// for (int i = 1 ; i <= tot ; ++ i) cout << h[i] << " " << g[i] << endl ;
cout << (S(n, 0) + 1) % P << endl ; return 0 ;
}

一想到 zzq 出这个题的年纪我还在玩泥巴,就知道自己退役预定了。

是啊,本来就是强行续命,所以无论结果怎么样也只能欣然接受了吧。