Several Algorithms of root Complex

发表于 |

I, as a ACMer, always take algorithm complexity into consideration when programming. Today, I introduce you some elegant algorithms of root Complex.

1. $s(n) = \sum_{i=1}^{n} \lfloor \frac{n}{i} \rfloor$

Since The range of $\lfloor \frac{n}{i} \rfloor$ contains at most $2\sqrt{n}$ . There may exist a algorithm of complexity $O(\sqrt{n})$.

1
2
3
4
5
6
7
8
LL getsum(LL n){ // The code is simple and easy to understand
    LL sum = 0;
    for(LL i=1,j;i<=n;i=j+1){ 
        j = n/(n/i);
        sum += (j-i+1)*(n/i);
    }
    return sum;
}

Actually, $s(n)$ donate the number of positive integer point under graph $xy=1$.

2. $\sigma_k(n) = \sum_{d|n} d^k$

  1. $\sigma_0(n)$ donate the number of divisors.
  2. $\sigma_1(n)$ donate the sum of divisors.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    LL mypow(LL x,LL n){
        LL r = 1;
        while(n){
            if(n&1) r=r*x;
            n>>=1;  x=x*x;
        }
        return r;
    }
    LL getr(LL n,LL k){
        LL r = 0,d;
        for(d=1;d*d<n;++d){
            if(n%d==0)  r += mypow(d,k) + mypow(n/d,k);
        }
        if(d*d == n) r+=mypow(d,k);
        return r;
    }

The code above is primary and trival.

3. $f(n) = \sum_{i=1}^n \sigma_k(i)$

$$f(n) = \sum_{i=1}^n \sigma_k(n) = \sum_{i=1}^n \sum_{d|i} d^k = \sum_{d=1} d^k \sum_i ^n[d|i] = \sum_{d=1} ^n d^k \lfloor \frac{n}{d} \rfloor$$

If we get $ts[n] = \sum_{i=1}^n i^k$, similar to problem 1, we have fllowing C++ code:

1
2
3
4
5
6
7
8
LL getf(LL n){
    LL sum = 0;
    for(LL i=1,j;i<=n;i=j+1){ 
        j = n/(n/i);
        sum += (ts[j]-ts[i-1])*(n/i);
    }
    return sum;
}

Actuall, we have
$$ts[n] = \left \{ \begin{array}{ll} \frac{n(n+1)}{2} & k=1 \\ \frac{n(n+1)(2n+1)}{6} & k=2 \\ \frac{n^2(n+1)^2}{4} & k=3 \\ \end{array} \right.$$
and for general

$$1^p+2^p+ \dots + n^p = \sum _{k=1} ^p \; (\; \sum_{j=1} ^ {k} (-1)^{k-j} C_k^j j^p \;) \; C _{n+1} ^{k+1}$$

you can see my blog for detail.

4. $g(n) = \sum_{i=1}^n\phi(i)$

Throughout this blog, $\phi(n)$ donate the Euler function unless explicitly stated.$\phi(n)$ counts the positive integers less than or equal to n that are relatively prime to n. Euler’s product formula:
$$\phi(n) = n \prod _{p|n}( 1-\frac{1}{p} )$$
where the product is over the distinct prime numbers dividing n.

Now, we begin to computer $g(n)$
$$g(n) = \sum_ {i=1}^n \phi(i) = \sum_{1 \leq x \leq y \leq n , gcd(x,y)=1} 1$$

we define
$$g_k(n) = \sum_ {i=1}^n \phi(i) = \sum_{1 \leq x \leq y \leq n , gcd(x,y)=k} 1 = f(\lfloor \frac{n}{k} \rfloor)$$

and $\sum_{i=1}^n g_k(i) = \sum_{1 \leq x \leq y \leq n} 1 = \frac{n(n+1)}{2}$ So we have

$$g(n) = \frac{n(n+1)}{2} - \sum_ {k=2}^n f(\lfloor \frac{n}{k} \rfloor)$$

Similar to problem 1,we have,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N=1000006;
LL ans[N];
void init(){
    memset(ans,-1,sizeof(ans));
    ans[1]=1;ans[2]=2;
}
LL getans(int n){
    if(n<N&&ans[n]!=-1) return ans[n];
    LL r = n*(n+1)/2;
    for(int i=2,j;i<=n;i=j+1){
        j = n/(n/i);
        r -= (j-i+1)*getans(n/i);
    }
    if(n<N) ans[n]=r;
    return r;
}

5. Problem hdu5608

If
$$n^2 -3n+2 = \sum_ {d|n} f(d)$$
calculate
$$h(n) = \sum_{i=1}^n f(i) \; mod \; 10^9+7$$

Since
$$\sum_{i=1}^n \sum_ {d|i} f(d) = \sum_{i=1}^n f(i) \lfloor \frac{n}{i} \rfloor = \sum_{i=1}^n h(\lfloor \frac{n}{i} \rfloor)$$
and we have,

$$\sum_{i=1}^n \sum_ {d|i} f(d) = \sum_{i=1}^n n^2-3n+2 = \sum_{i=1}^n (n-1)(n-2) = \frac{n(n-1)(n-2)}{3}$$

by conditon. Hence,
$$h(n) = \frac{n(n-1)(n-2)}{3} - \sum_{i=2}^n h(\lfloor \frac{n}{i} \rfloor)$$

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
//#pragma comment(linker,"/STACK:10240000,10240000")
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define clr(a,b) memset(a,b,sizeof(a))
#define MP make_pair
#define PB push_back
#define lrt rt<<1
#define rrt rt<<1|1
#define lson l,m,lrt
#define rson m+1,r,rrt
/*------ Welcome to visit blog of dna049: http://dna049.com ------*/
const int N=1000006;
const int M = 1e9+7;
const int inv3 = (M+1)/3;
int ans[N];
map<int,int> mp;
void init(){
    for(int i=0;i<N;++i){
        ans[i] = LL(i-1)*(i-2)%M;
    }
    for(int i=1;i<N;++i){  // Pretreatment acceleration
        for(int j=i<<1;j<N;j+=i){
            ans[j] -= ans[i];
            if(ans[j] < 0) ans[j] += M;
        }
    }
    for(int i=2;i<N;++i){
        ans[i] += ans[i-1];
        if(ans[i] > M)  ans[i] -= M;
    }
}
int getans(int n){ 
    if(n<N) return ans[n];
    map<int,int>::iterator it = mp.find(n); //Memory search
    if (it != mp.end())  return it->second;
    int r = LL(n)*(n-1)%M*(n-2)%M*inv3%M;
    for(int i=2,j;i<=n;i=j+1){
        j = n/(n/i);
        r -= LL(j-i+1)*getans(n/i)%M;
        if(r<0) r+=M;
    }
    mp.insert(pair<int,int>(n,r));
    return r;
}
int main(){
//    freopen("/Users/c10110057/Desktop/AC/in","r",stdin);
    init();
    int T,n;
    cin>>T;
    while(T--){
        scanf("%d",&n);
        cout<<getans(n)<<endl;
    }
    return 0;
}

6. Note

All C++ code above should be changed to fit different demands.Thanks Zimpha who provides some problems and ideas two years old.