LibreOJ 6053 简单的函数

发表于 | 分类于

Description

今有一积性函数\(f(x)\)，满足以下性质

  • \(f(1) = 1\)。
  • 对任意质数\(p\)和正整数\(c\)，有\(f(p^c) = p\oplus c\)。

给定正整数\(n\)，求\(\sum_{i = 1}^n f(i)\)，答案模1000000007。

\(n\leq 10^{10}\)。

Solution

算是一道不那么水的Min_25筛板子题？

Min_25筛最核心的地方就是对于质数的答案求前缀和。那么我们考虑对任意质数\(p\)，\(f(p)\)的取值。然后我们会发现除了\(2\)以外的所有质数都是奇数，所以对于\(2\)有\(f(p) = p + 1\)，对其他质数有\(f(p) = p - 1\)。

那么我们把质数的答案分为两部分考虑：一部分是\(p\)，另一部分是后面的加减一。前面一部分就是质数本身的和，几乎就是最简单的Min_25筛；后面也不难，只需要对于小于等于2的情况特判一下就完了。

然后下面就是标准的Min_25筛了……Min_25筛真香！

Code

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
const int maxn = 200005;
using ll = long long;
const ll ha = 1000000007LL;
ll sqr(ll x) {
  ll ret = 1;
  while((ret + 1LL) * (ret + 1LL) <= x) ret ++;
  return ret;
}

ll n, S; int cnt;
ll A[2][maxn]; ll prm[maxn];
void sieve_0() {
  S = sqr(n); cnt = 0;
  for(int i = 1; i <= S; i ++) {
    A[0][i] = i;
  }
  for(int i = 1; i <= S; i ++) {
    A[1][i] = (n / (ll(i))) % ha;
  }
  for(int i = 2; i <= S; i ++) {
    if(A[0][i - 1] == A[0][i]) continue;
    prm[++ cnt] = i;
    ll lim = (ll(i)) * (ll(i)), v = A[0][i - 1];
    for(int j = 1; j <= S / i; j ++) {
      ll delta = (A[1][j * i] - v + ha) % ha;
      A[1][j] = (A[1][j] - delta + ha) % ha;
    }
    for(int j = S / i + 1; j <= S; j ++) {
      ll src = n / ((ll(j)) * (ll(i)));
      if(src < (ll)i) break;
      ll delta = (A[0][src] - v + ha) % ha;
      A[1][j] = (A[1][j] - delta + ha) % ha;
    }
    for(int j = S; (ll)j >= lim; j --) {
      ll delta = (A[0][j / i] - v + ha) % ha;
      A[0][j] = (A[0][j] - delta + ha) % ha;
    }
  }
  prm[++ cnt] = S + 1;
}
ll B[2][maxn];
ll S1(ll x) {
  ll a = x, b = x + 1LL;
  if(x & 1LL) {
    b >>= 1;
  } else {
    a >>= 1;
  }
  a %= ha; b %= ha;
  return (a * b) % ha;
}
void sieve_1() {
  S = sqr(n); cnt = 0;
  for(int i = 1; i <= S; i ++) {
    B[0][i] = S1(i);
  }
  for(int i = 1; i <= S; i ++) {
    B[1][i] = S1(n / (ll(i)));
  }
  for(int i = 2; i <= S; i ++) {
    if(B[0][i - 1] == B[0][i]) continue;
    prm[++ cnt] = i;
    ll lim = (ll(i)) * (ll(i)), v = B[0][i - 1];
    for(int j = 1; j <= S / i; j ++) {
      ll delta = (B[1][j * i] - v + ha) % ha;
      delta = (delta * (ll(i))) % ha;
      B[1][j] = (B[1][j] - delta + ha) % ha;
    }
    for(int j = S / i + 1; j <= S; j ++) {
      ll src = n / ((ll(j)) * (ll(i)));
      if(src < (ll)i) break;
      ll delta = (B[0][src] - v + ha) % ha;
      delta = (delta * (ll(i))) % ha;
      B[1][j] = (B[1][j] - delta + ha) % ha;
    }
    for(int j = S; (ll)j >= lim; j --) {
      ll delta = (B[0][j / i] - v + ha) % ha;
      delta = (delta * (ll(i))) % ha;
      B[0][j] = (B[0][j] - delta + ha) % ha;
    }
  }
  prm[++ cnt] = S + 1;
#ifdef LOCAL
  for(int i = 1; i <= cnt; i ++) {
    printf("prm[%d] : %lld\n", i, prm[i]);
  }
  for(int i = 1; i <= S; i ++) {
    printf("B[%d] : %lld\n", i, B[0][i]);
  }
  for(int i = S; i >= 1; i --) {
    printf("B[%lld] : %lld\n", n / (ll(i)), B[1][i]);
  }
#endif
}
ll query_0(ll x) {
  if(x <= 1LL) return 0;
  if(x == 2LL) return 1;
  ll ret;
  if(x <= S) {
    ret = A[0][x];
  } else {
    ret = A[1][n / x];
  }
  ret --;
  ret = (2LL - ret + ha) % ha;
  return ret;
}
ll query_1(ll x) {
  if(x <= S) {
    return B[0][x];
  } else {
    return B[1][n / x];
  }
}
ll calc(ll m, int x) {
  if(m < prm[x]) return 0;
  ll ret = (query_0(m) + query_1(m)) % ha;
  ret = (ret - (query_0(prm[x] - 1) + query_1(prm[x] - 1)) % ha + ha) % ha;
  for(int i = x; i <= cnt; i ++) {
    ll st = prm[i];
    if(st * prm[i] > m) break;
    for(int j = 1; ; j ++) {
      if(st * prm[i] > m) break;
      ll delta = ((calc(m / st, i + 1) * (prm[i] ^ (ll(j)))) % ha + (prm[i] ^ (ll(j + 1)))) % ha;
      ret = (ret + delta) % ha;
      st *= prm[i];
    }
  }
  return ret;
}

int main() {
  scanf("%lld", &n);
  sieve_0(); sieve_1();
  printf("%lld\n", (1LL + calc(n, 1)) % ha);
  return 0;
}