数论函数与数论恒等式

省选前最后要学的新知识了，下周开始模板复习。

---

1. 取整函数

$$r=\lfloor r\rfloor +\{r\}, \lfloor r\rfloor\in Z,\{r\}\in [0,1)$$

$$r = \lceil r\rceil-c,\lceil r\rceil\in Z,c\in [0,1)$$

几个不等式：

插入/删除取整号

1. $r<n\iff \lfloor r\rfloor < n$
   证明：
   

   $$r<n\iff n-\lfloor r\rfloor>\{r\}\ge 0\iff \lfloor r\rfloor<n$$
   同理有：
   $$r > n \iff \lceil r\rceil>n$$

2. $r\le n\iff \lceil r\rceil\le n$
   证明:
   

   $$r\le n\iff \lceil r\rceil-c\le n\iff \lceil r\rceil-n\le c<1\\\iff \lceil r\rceil<n+1\iff \lceil r\rceil\le n$$
   同理有：
   $$r\ge n\iff\lfloor r\rfloor\ge n$$

整除边界值

$$\left\lfloor \frac p i\right\rfloor=\left\lfloor \frac p k\right\rfloor\Rightarrow k\le \left\lfloor \frac p {\left\lfloor \frac p i\right\rfloor}\right\rfloor$$

证明：

由于：

$$\frac p {i} = \biggl\lfloor\frac p {i}\biggr\rfloor+c_1\\ \frac p {k}=\biggl\lfloor\frac p {k}\biggr\rfloor+c_2$$

满足$c\in[0,1)$，联立以上若干式，可得：

$$0\le \frac p {k}-\biggl\lfloor\frac p {i}\biggr\rfloor<1$$

满足：

$$k\le \frac p {\biggl\lfloor\frac p {i}\biggr\rfloor}\iff k\le \left\lfloor \frac p {\left\lfloor \frac p i\right\rfloor}\right\rfloor$$

2. 数论函数

欧拉函数

$$\varphi(i)=\sum_{k\le i}[(i,k)=1]$$

性质： 欧拉函数是积性函数。

证明：

$$\varphi(ij)=\sum_{k\le ij}[(ij,k)=1]=\sum_{k\le ij}[(i,k)=1][(j,k)=1]\\=\sum_{j(p-1)+q\le ij,q\le j}[(i,j(p-1)+q)=1][(j,j(p-1)+q)=1]\\=\sum_{(p-1)+ q/j\le i,q\le j}[(i,j(p-1)+q)=1][(j,q)=1]$$

设$k=(p-1)+q/j$，则原式为：

$$\sum_{k\le i,q\le j}[(i,kj)=1][(j,q)=1]$$

其中$k$是一个有理数，因为素数有无穷多个，对于任意大的$i,j$，总可以找到一个素数作为模。容易利用同余式证明模意义下存在：

$$(i,j)=1\ then\ (i,kj)=1\iff (i,k)=1$$

则原式就是：

$$\sum_{k\le i,q\le j}[(i,k)=1][(j,q)=1]$$

注意到：

$$\varphi(i)\varphi(j)=\left(\sum_{k\le i}[(i,k)=1]\right)\left(\sum_{k\le j}[(j,k)=1]\right)=\sum_{k\le i, p\le j}[(i,k)=1][(j,p)=1]\\=\sum_{k\le i, p\le j}[(i,k)=1][(j,p)=1]$$

则有：$\forall(m,n)=1,\varphi(mn)=\varphi(m)\varphi(n)$。

因子个数函数

$$d(n) = \sum_i[i|n]$$

性质： $d(i)=\prod (p_k(i)+1)$。证明依赖唯一分解定理和乘法原理。其中$p_k(i)$表示第$k$个素数在$i$的唯一分解中的幂次。

函数$d$与另一个函数$e(n)$密切相关，它被定义为$n$的最小素因子在唯一分解中的幂次。

下列性质给出了$O(n)$求解$d$函数的方法。

• $j$为$ij$最小的素因子，$d(ij)=\frac {d(i)(e(i)+2)}{(e(i)+1)}$
• $(i,j)=1\Rightarrow d(ij)=d(i)*d(j)$

而$e(i)$的维护十分方便，因此可以得到：

const int MAXN = 50005;
int prime[MAXN], not_prime[MAXN], e[MAXN], d[MAXN], top = 0;
void get_prime(int n)
{
    e[1] = 0, d[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!not_prime[i]) { prime[++top] = i, e[i] = 1, d[i] = 2; }
        for (int j = 1; j <= top && prime[j]*i <= n; j++) {
            not_prime[prime[j]*i] = 1;
            if (i%prime[j] == 0) {
                d[prime[j]*i] = d[i]/(e[i]+1)*(e[i]+2);
                e[prime[j]*i] = e[i]+1;
                break;
            }
            e[prime[j]*i] = 1;
            d[prime[j]*i] = d[i]*d[prime[j]];
        }
    }
    for (int i = 1; i <= 20; i++)
        cout << d[i] << " ";
    puts("");
}

莫比乌斯函数

$$\mu(d)=[\forall p,p(i)\le 1](-1)^{\sum p(i)}$$

符号$p(k)$为k中蕴含素因子p的个数。

性质：

1. 莫比乌斯函数是积性函数
2. $\sum_{d|n}\mu(d)=[n=1]$
3. (反演定理)：
   $$F(n)=\sum_{d|n}f(n)\iff f(n)=\sum_{d|n}\mu(\frac n d)F(d)$$
   证明：
   $$\sum_{d|n}\mu(\frac n d)F(d)=\sum_{d|n}\mu(\frac n d)\sum_{k|d}f(k)\\=\sum_{k|n}f(k)\sum_{k|d,d|n}\mu(\frac n d)$$
   令$d=pk, q = n/k$，原式=
   $$\sum_{k|n}f(k)\sum_{pk|n}\mu(\frac n {pk})=\sum_{k|n}f(k)\sum_{p|q}\mu(\frac q {p})\\=\sum_{k|n}f(k)[q=1]=f(n)$$
4. 另一种形式的反演定理：
   $$F(i)=\sum_{k\ge 1}f(ki)\iff f(i)=\sum_{k\ge 1}\mu(k)F(ki)$$

处理的技巧

参见：http://blog.csdn.net/oiljt12138/article/details/70188437