当前位置：网站首页>Du Jiao sieve

Du Jiao sieve

2022-07-25 06:36:00 【51CTO】

The core of Du Jiao sieve

purpose ：

Used in less than linear time , Be more efficient Integrability function Of The prefix and

Algorithm ：

To put it simply Divide and divide + Dirichlet convolution + Linear sieve

The formula ：

The time complexity will be reduced to

Integrability function

If p and q Mutual quality and said f It's a product function

If for any p and q There are Then Cheng f Is a completely integrable function

Common product function

Divisor function , Express n The divisor of k The sum of powers , Be careful And Is different .
About several number functions Express n The approximate number of , Generally, it also forms d(n).
Approximations and functions , Express n And .
Euler function No greater than n Cut with n The number of positive integers of the Shanghai index , in addition And for positive integers n>2 Come on It's even .
Mobius function , In the penalty of Dirichlet convolution, it is reciprocal with the identity function . For the square free factor number , Yes , For numbers with square factors, there are .
Meta function , Multiplicative unit of Dirichlet convolution , Complete integrability
Identity function Complete integrability
Unit function , Complete integrability
power function Complete integrability

Two important theorems ：

Dirichlet convolution

And f(n) and g(n) Are all integral functions , that Satisfy , Commutative law and associative law , Additive distribution rate

Mobius inversion ：

Dujiao sieve

The formula ：

Push a specific formula ：

Here we are going to use properties ：

enumeration

Make

       
       // Code 
       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       typedef 
       
       long 
       
       long 
       
       ll;
       
       const 
       
       int 
       
       maxn 
       
       = 
       
       5e6
       
       +
       
       7;         
       
       // exceed n^(2/3), Big enough 
       
       int 
       
       prime[
       
       maxn];                
       
       // Record prime 
       
       bool 
       
       vis[
       
       maxn];                 
       
       // Record whether it is sifted ;
       
       int 
       
       mu[
       
       maxn];                   
       
       // Mobius function value 
       
       ll 
       
       phi[
       
       maxn];                   
       
       // Euler function value 
       
       unordered_map
       
       <
       
       int,
       
       int
       
       > 
       
       summu;   
       
       // Mobius function prefix and 
       
       unordered_map
       
       <
       
       int,
       
       ll
       
       > 
       
       sumphi;   
       
       // Euler function prefix and 
       
       void 
       
       init(){             
       
       // Linear sieve precomputation part of the answer 
       
       int 
       
       cnt 
       
       = 
       
       0;
       
       vis[
       
       0] 
       
       = 
       
       vis[
       
       1] 
       
       = 
       
       1;
       
       mu[
       
       1] 
       
       = 
       
       phi[
       
       1] 
       
       = 
       
       1;
       
       for(
       
       int 
       
       i
       
       =
       
       2;
       
       i
       
       <
       
       maxn;
       
       i
       
       ++){
       
       if(
       
       !
       
       vis[
       
       i]){
       
       prime[
       
       cnt
       
       ++] 
       
       = 
       
       i;
       
       mu[
       
       i] 
       
       = 
       
       -
       
       1;
       
       phi[
       
       i] 
       
       = 
       
       i
       
       -
       
       1;
       
        }
       
       for(
       
       int 
       
       j
       
       =
       
       0;
       
       j
       
       <
       
       cnt 
       
       && 
       
       i
       
       *
       
       prime[
       
       j]
       
       <
       
       maxn;
       
       j
       
       ++){
       
       vis[
       
       i
       
       *
       
       prime[
       
       j]] 
       
       = 
       
       1;
       
       if(
       
       i
       
       %
       
       prime[
       
       j]){
       
       mu[
       
       i
       
       *
       
       prime[
       
       j]] 
       
       = 
       
       -
       
       mu[
       
       i];
       
       phi[
       
       i
       
       *
       
       prime[
       
       j]] 
       
       = 
       
       phi[
       
       i]
       
       *
       
       phi[
       
       prime[
       
       j]];
       
      }
       
       else{
       
       mu[
       
       i
       
       *
       
       prime[
       
       j]] 
       
       = 
       
       0;
       
       phi[
       
       i
       
       *
       
       prime[
       
       j]] 
       
       = 
       
       phi[
       
       i]
       
       *
       
       prime[
       
       j];
       
       break;
       
      }
       
    }
       
  }
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <
       
       maxn;
       
       i
       
       ++){       
       
       // Last ,mu[] and phi[] Change to record 1~maxn And .
       
       mu[
       
       i] 
       
       += 
       
       mu[
       
       i
       
       -
       
       1];
       
       phi[
       
       i] 
       
       += 
       
       phi[
       
       i
       
       -
       
       1];
       
    }
       
}
       
       int 
       
       gsum(
       
       int 
       
       x){             
       
       // g(i) And 
       
       return 
       
       x;
       
}
       
       ll 
       
       getsmu(
       
       int 
       
       x){
       
       if(
       
       x 
       
       < 
       
       maxn) 
       
       return 
       
       mu[
       
       x];      
       
       // Precomputation 
       
       if(
       
       summu[
       
       x]) 
       
       return 
       
       summu[
       
       x];   
       
       // Memorize 
       
       ll 
       
       ans 
       
       = 
       
       1;                    
       
       // Du Jiao sieve formula  1
       
       for(
       
       ll 
       
       l
       
       =
       
       2,
       
       r;
       
       l
       
       <=
       
       x;
       
       l
       
       =
       
       r
       
       +
       
       1){      
       
       // Calculate Duchenne's sieve formula by dividing into blocks 
       
       r 
       
       = 
       
       x
       
       /(
       
       x
       
       /
       
       l);
       
       ans 
       
       -= (
       
       gsum(
       
       r)
       
       -
       
       gsum(
       
       l
       
       -
       
       1))
       
       *
       
       getsmu(
       
       x
       
       /
       
       l);
       
  }
       
       return 
       
       summu[
       
       x] 
       
       = 
       
       ans
       
       /
       
       gsum(
       
       1);
       
}
       
       ll 
       
       getsphi(
       
       int 
       
       x){
       
       if(
       
       x 
       
       < 
       
       maxn) 
       
       return 
       
       phi[
       
       x];
       
       if(
       
       sumphi[
       
       x]) 
       
       return 
       
       sumphi[
       
       x];  
       
       // Memorize , Every sumphi[x] Just count once 
       
       ll 
       
       ans 
       
       = 
       
       x
       
       *((
       
       ll)
       
       x
       
       +
       
       1)
       
       /
       
       2;          
       
       // Du Jiao sieve formula  n(n+1)/2
       
       for(
       
       ll 
       
       l
       
       =
       
       2,
       
       r;
       
       l
       
       <=
       
       x;
       
       l
       
       =
       
       r
       
       +
       
       1){       
       
       // Calculate Duchenne's sieve formula by dividing into blocks , Here it is  sqrt(x) Time 
       
       r 
       
       = 
       
       x
       
       /(
       
       x
       
       /
       
       l);
       
       ans 
       
       -= (
       
       gsum(
       
       r)
       
       -
       
       gsum(
       
       l
       
       -
       
       1))
       
       *
       
       getsphi(
       
       x
       
       /
       
       l);
       
  }
       
       return 
       
       sumphi[
       
       x] 
       
       = 
       
       ans
       
       /
       
       gsum(
       
       1);
       
}
       
       int 
       
       main(){
       
       init();  
       
       // Pre calculate a part with a linear sieve 
       
       int 
       
       t;
       
       scanf(
       
       "%d",
       
       &
       
       t);
       
       while(
       
       t
       
       --){
       
       int 
       
       n;
       
       scanf(
       
       "%d",
       
       &
       
       n);
       
       printf(
       
       "%lld %lld\n",
       
       getsphi(
       
       n),
       
       getsmu(
       
       n));
       
  }
       
       return 
       
       0;
       
}
      
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.