LibreOJ 6053.简单的函数

注意到质数除了 22 都是奇数,故 f(p)=p1+2[p=2]f(p) = p - 1 + 2[p=2]

于是有 G0,0(n)=n+1,G0,1=(n+2)(n1)2G_{0,0}(n) = -n + 1,G_{0,1} = \dfrac{(n+2)(n-1)}2
然后对 22 讨论一下即可。

代码:

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
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const long long N = 1e10;
const int MX = 1e5;
const int mod = 1e9 + 7;
const int inv = 5e8 + 4;
long long n;
int lim;
int vis[MX + 5],prime[MX + 5],cnt,Gprime[MX + 5];
int tot,le[MX + 5],ge[MX + 5];
long long lis[2 * MX + 5];
int G[2 * MX + 5][2],Fprime[2 * MX + 5];
inline int &id(long long x)
{
return x <= lim ? le[x] : ge[n / x];
}
int F(int k,long long n)
{
if(n < prime[k] || n <= 1)
return 0;
int ret = (Fprime[id(n)] - (Gprime[k - 1] - (k - 1) + mod) % mod + mod) % mod;
if(k == 1)
ret += 2;
for(register int i = k;i <= cnt && (long long)prime[i] * prime[i] <= n;++i)
{
long long pw = prime[i],pw2 = (long long)prime[i] * prime[i];
for(register int c = 1;pw2 <= n;++c,pw = pw2,pw2 *= prime[i])
ret = (ret + (long long)(prime[i] ^ c) * F(i + 1,n / pw) % mod + (prime[i] ^ c + 1)) % mod;
}
return ret;
}
int main()
{
for(register int i = 2;i <= MX;++i)
{
if(!vis[i])
prime[++cnt] = i,Gprime[cnt] = (Gprime[cnt - 1] + i) % mod;
for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
}
}
scanf("%lld",&n),lim = sqrt(n);
for(register long long l = 1,r;l <= n;l = r + 1)
{
r = n / (n / l);
lis[id(n / l) = ++tot] = n / l;
G[tot][0] = (n / l % mod - 1 + mod) % mod,G[tot][1] = (n / l % mod + 2) * (n / l % mod - 1 + mod) % mod * inv % mod;
}
for(register int k = 1;k <= cnt;++k)
{
int p = prime[k];
long long s = (long long)p * p;
for(register int i = 1;lis[i] >= s;++i)
G[i][0] = (G[i][0] - (G[id(lis[i] / p)][0] - (k - 1) + mod) % mod + mod) % mod,
G[i][1] = (G[i][1] - (long long)p * ((G[id(lis[i] / p)][1] - Gprime[k - 1] + mod) % mod) % mod + mod) % mod;
}
for(register int i = 1;i <= tot;++i)
Fprime[i] = (G[i][1] - G[i][0] + mod) % mod;
printf("%d\n",(F(1,n) + 1) % mod);
}