LibreOJ - 6053（积性函数前缀和,pn筛角度）

题意：

n<=1e10
思路： 积性函数性质,pn筛角度
易知f(i)是积性函数。
设$f=g\ast h,其中\ast 表示狄利克雷卷积$
试着构造一下h和g,由于 f ( p ) = { p − 1 = φ ( p ) , p > 2 p + 1 , p = 2 f(p)=

f(p)={p−1=φ(p)p+1​,p>2,p=2​
考虑p=2时，f固定有f(2^k)的贡献，构造 g ( x ) = { φ ( x ) , x ∤ 2 3 φ ( x ) , x ∣ 2 g(x)=

{φ(x),x∤23φ(x),x∣2" role="presentation" style="position: relative;">{φ(x)3φ(x),x∤2,x∣2$$\{\begin{array}{ll}\phi (x)& ,x\nmid 2\\ 3\phi (x)& ,x\mid 2\end{array}$$

g(x)={φ(x)3φ(x)​,x∤2,x∣2​
由积性函数定义，有$f(p)=h(p)g(1)+h(1)g(h)和f(1)=h(1)g(1),而h(p)=f(p),所以h(p)=0,h(1)=1$。
也就是说h(x)只可能在x为powerful number时取到非零数，而pn数量级是$\sqrt{n}$的，考虑pn筛。
${\sum }_{i=1}^{n}f(i)={\sum }_{i=1}^{n}h(i){\sum }_{j=1}^{\lfloor \frac{n}{i}\rfloor }g(j)$
接下来是g(i)的前缀和如何快速求
${\sum }_{i=1}^{n}g(i)={\sum }_{i=1}^n\phi (i)+2{\sum }_{i=1}^{\lfloor \frac{n}{2}\rfloor }\phi (2i)$，前半部分用杜教筛可以在$O(n^{\frac{2}{3}})解决。$
现在解决后面的求和问题，我们设$S(n)={\sum }_{i=1}^n\phi (2i)$
利用积性函数性质并且尽量往前缀和上靠
当n为偶数时，考虑把$\phi (2i)的i分为奇数和偶数两部分求和$
$$\begin{gathered} S(n)={\sum }_{i=1}^{\frac{n}{2}}(\phi (2i)+\phi (2(n+i)) \\ ={\sum }_{i=1}^{\frac{n}{2}}(\phi (2(2i-1))+\phi (2\ast 2i)) \\ ={\sum }_{i=1}^{\frac{n}{2}}(\phi (2i-1)+2\phi (2i)) \\ ={\sum }_{i=1}^{\frac{n}{2}}(\phi (2i-1)+\phi (2i))+{\sum }_{i=1}^{\frac{n}{2}}\phi (2i) \\ ={\sum }_{i=1}^n\phi (i)+S(\frac{n}{2}) \end{gathered}$$
当n为奇数时，考虑往上面的式子转化
$S(n)=S(n-1)+\phi (2n)$,而S(n-1)上面已经推出来了
继续化简
$$\begin{gathered} S(n)=S(\frac{n-1}{2})+{\sum }_{i=1}^{n-1}\phi (i)+\phi (2n) \\ =S(\frac{n-1}{2})+{\sum }_{i=1}^{n-1}\phi (i)+\phi (n)(2和n互质) \\ =S(\frac{n-1}{2})+{\sum }_{i=1}^n\phi (i) \end{gathered}$$
综上:
$S(n)=S(\lfloor \frac{n}{2}\rfloor )+{\sum }_{i=1}^n\phi (i)$
于是可以递归求解了，最多logn层
所以g(i)的前缀和问题解决了,即
${\sum }_{i=1}^{n}g(i)={\sum }_{i=1}^n\phi (i)+2S(\frac{n}{2})$

现在解决h(x)，我们只关心每个$h(p^k)，其中k>1$，因为h(x)是积性函数，其他pn数可以由此组合出来。
考虑$f(p^k)={\sum }_{i+j=k,0<=i<=k}h(p^i)g(p^j),其中g(p^j)=p^{j-1}(p-1)$，且g(1)=1
即$h(p^k)=f(p^k)-{\sum }_{i+j=k,0<=i<=k-1}h(p^i)g(p^j)$暴力算即可，不超过logn项。
而h(x)有值的地方不超过$\sqrt{n}$，这部分复杂度$\sqrt{n}logn$,复杂度瓶颈应该在杜教筛$O(n^{2/3})$那。

PS:多观察函数性质，特别是积性函数，和已知的一些数论函数的性质或者数论函数本身的定义。多往前面已求出来的问题上思考转化。
会爆longlong，博主直接用int128了。

const int N=1e6+5;
const int mod=1e9+7;
const double eps=1e-8;
int ans,n,limit,sq;
int p[80001], tot,h[N][41],eu[N],SUM[N],S1[N];
bool v[N];
int ni[51],gg[51];
map<int, int >mpS1,mpeu;
int read(){
    ll x = 0 ,f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
void print(ll x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) print(x/10);
    putchar(x % 10 + '0');
}
int qsm(int a, int b){
    a%=mod;
    int ans = 1, temp = a;
    while (b){
        if (b & 1) ans = ans*temp%mod;
        temp = temp*temp%mod;
        b >>= 1;
    }
    return ans;
}
void ini(){//有关全局n的预处理，h(p^k)的预处理(k>1)
    for(sq=1;p[sq]*p[sq]<=n&&sq+1<=tot ;sq++);
     _for(i,1,sq){
        gg[0] = 1;
        if( p[i]==2 ) gg[1] = 3;
        else gg[1] = eu[p[i]]%mod;
        h[i][0] = 1;
        h[i][1] = 0;
        for(int j=p[i]*p[i],e=2;j<=n;j*=p[i],e++){
            gg[e] = gg[e-1]%mod*p[i]%mod;
            h[i][e] = (p[i]^e)%mod;
            for(int k=0 ;k<e ;k++){
                h[i][e] = (h[i][e] - h[i][k]*gg[e-k]%mod+mod)%mod;
            }
        }
    }
}
void shai(int n){
    _for(i,1,41) ni[i] = qsm(i,mod-2);
    v[1] = eu[1] = 1;
    _for(i, 2, n){
        if (!v[i]){
            p[++tot] = i;
            eu[i] = i - 1;
        }
        _for(j, 1, tot){
            if (i * p[j] > n) break;
            v[i * p[j]] = 1;
            if (i % p[j] == 0){
                eu[i * p[j]] = eu[i] * p[j];
                break;
            }
            eu[i * p[j]] = eu[i] * (p[j] - 1);
        }
    }
    _for(i, 1, n) {
        SUM[i] = (eu[i]%mod + SUM[i-1])%mod;
    }
}
int geteu(int x){
    if (x <= 1e6) return SUM[x];
    if (mpeu[x]) return mpeu[x];
    int ans = x %mod* (x + 1)%mod %mod*ni[2]%mod;
    for (int l = 2, r = 0; l <= x; l = r + 1){
        r = x / (x / l);
        ans -= (r - l + 1)%mod * geteu(x / l)%mod;
        ans += mod;
        ans %= mod;
    }
    return mpeu[x] = ans;
}
int get_sum(int x){
    if( !x ) return 0;
    if (mpS1[x]) return mpS1[x];
    if (x==1) return mpS1[x] = 1;
    return mpS1[x] = (get_sum(x/2) + geteu(x))%mod;
}
void dfs(int cur,int val,int num){//累计到第num-1个质数的乘积为cur,h(cur) = val
    ans = (ans + val*(geteu(n/cur)+get_sum(n/cur/2)*2%mod)%mod)%mod;
    for(int i=num ;i<=sq ;i++){
        if( p[i] * p[i] > n/cur ) break;
        for(int t=p[i]*p[i] ,e=2; cur*t<=n ;t *= p[i],e++){
            dfs(cur*t,val*h[i][e]%mod,i+1);
        }        
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif  
    // IOS;
    shai(1e6);
    // cin>>n;
    n = read();
    ini();
    dfs(1,1,1);
    print(ans);
}
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