数论习题

数学，数论

Codeforces757E.Bash Plays With Functions (积性函数)

$Description$

$$f_0(n)=\sum_{u\times v=n}[(u,v)=1]\\ f_{r+1}(n)=\sum_{u\times v=n}\frac{f_r(u)+f_r(v)}{2}$$

$Solution$

　　首先将$f_r$的式子化为

$$f_{r+1}(n)=\sum_{d|n}f_r(d)$$
　　即$f_{r+1}(n)$为$f_r(n)$与$g(n)=1$的狄利克雷卷积。
　　因为n的所有质因子之间对$f_0(n)$的贡献是独立的，所以显然$f_0(n)$为积性函数（为什么我还是不懂。。），那么$f_r(n)$也为积性函数。
　　于是可以对每个质因子单独计算，这样狄利克雷卷积就可以化成求和
$$f_{r+1}(p^k)=\sum_{i=0}^kf_r(p^i)$$
　　（$p^k$的所有因子即$p^i,i=0,1,\ldots,k$）
　　同时可以发现$f_0(p^k)=[k\neq 0]+1$，即$f_0(p^k)$的值与因子p无关，只与次数有关。
　　那么DP，用$dp[i][j]$表示$f_i(p^j)$，则$dp[i][j]=\sum_{k=0}^jdp[i-1][k]$。
　　询问时对$n$分解质因数即可。
　　Code.

BZOJ.2301.[HAOI2011]Problem B (莫比乌斯反演)

$Description$

　　求$\sum_{i=a}^b\sum_{j=c}^d[(i,j)=k]$

$Solution$

　　首先是把下界作为1.可以化为求

$$\sum_{i=1}^{\lfloor\frac{N}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{M}{k}\rfloor}[(i,j)=1]$$
说明：大概就我不能直接看出来了。。
　　首先要求$[1,N]$中有多少$i，i|k$，再求[1,j]中有多少$j，j|k且(i,j)=1$，显然这个$i,j$的上界就分别是$\lfloor\frac{N}{k}\rfloor,\lfloor\frac{M}{k}\rfloor$，答案就是$(i,j)=1$的$(i,j)$数对个数。
　　现在考虑如何求上面的式子。
　　由莫比乌斯反演，有
$$F(d)=\sum_{d|n}f(n)\Leftrightarrow f(d)=\sum_{d|n}\mu(\frac{n}{d})F(n)$$
　　设$f[i]$为满足$gcd(x,y)=i$的$(x,y)$对数，其中$1\leq x\leq b,1\leq y\leq d$；
　　$F[i]$为满足$i|gcd(x,y)$的$(x,y)$对数，其中$1\leq x\leq b,1\leq y\leq d$。
　　显然有$F[i]=\sum_{i|n}f[n]\Rightarrow f[i]=\sum_{i|n}\mu(\frac{n}{i})F[n]$
　　又显然有$F[i]=\lfloor\frac{b}{i}\rfloor\lfloor\frac{d}{i}\rfloor$，那么
$$f[i]=\sum_{i|n,1\leq n\leq min(b,d)}\mu(\frac{n}{i})\lfloor\frac{b}{n}\rfloor\lfloor\frac{d}{n}\rfloor$$
　　令$k=\frac{n}{i}$，即$n=ki$，令$b'=\frac{b}{i},d'=\frac{d}{i}$，则
$$f[i]=\sum_{k=1}^{min(b',d')}\mu(k)\lfloor\frac{b'}{k}\rfloor\lfloor\frac{d'}{k}\rfloor$$
　　(本题i就是1。)
　　上面这个式子还是$O(n^2)$的。。还是要分块计算。
　　Code.

HDU.5628.Clarke and math (狄利克雷卷积)

$Description$

　　

$$g(i)=\sum_{i_1|i}\sum_{i_2|i_1}\sum_{i_3|i_2}\cdots\sum_{i_k|i_{k-1}}f(i_k)\ mod\ 1000000007$$
　　给出$n,k,f[1\sim n]$，求$g[1\sim n]$.

$Solution$

　　首先狄利克雷卷积(Dirichlet Product)：设$f(n),g(n)$是两个数论函数，它们的Dirichlet乘积也是一个数论函数，

$$h(n)=\sum_{d|n}f(d)g(\frac{n}{d})$$
　　简记为$h(n)=f(n)*g(n)$。

狄利克雷卷积有几个性质：
　　1. 满足交换律 $f*g=g*f$
　　2. 满足结合律 $(f*g)*h=f*(g*h)$
　　3. 满足分配率 $f*(g+h)=f*g+f*h$
　　4. 存在单位元$e$，使得$e*f=f*e=f$

　　回到本题。设$I(x)=1$.
　　将式子依次展开
　　$f'(i_{k-1})=\sum_{i_k|i_{k-1}}f(i_k)=\sum_{i_k|i_{k-1}}f(i_k)*I(\frac{i_{k-1}}{i_k})$，即$f'=f*I$.
　　$f''(i_{k-2})=\sum_{i_{k-1}|i_{k-2}}f'(i_k-1)=\sum_{i_{k-1}|i_{k-2}}f'(i_k-1)I(\frac{i_{k-2}}{i_{k-1}})$，即$f''=f'*I$.
　　$\ldots$
　　这样下去可以得到$g=I*I*I*\cdots*I*f(k个I)$。由于狄利克雷卷积满足结合律，所以$k个I$的狄利克雷卷积可以用快速幂$logk$计算。
　　计算狄利克雷卷积时，如果对每个$g(i),1\leq i\leq n$都按照定义枚举其约数计算，时间肯定爆炸。所以可以枚举约数，再枚举这些约数可以对哪些值给出贡献，那么计算一次狄利克雷卷积的复杂度就是$O(nlogn)$，总复杂度$O(nlognlogk)$。
　　Code.

HDU.5698.function (杜教筛)

$Description$

　　$n^2-3n+2=\sum_{d|n}f(d)$
　　求$\sum_{i=1}^nf(i)\ mod \ 10^9+7$.

$Solution$

　　参考.
　　设$g(n)=n^2-3n+2$，那么$f*I=g$。
　　如果狄利克雷卷积中左边的一个函数是待求前缀和的，而另外两个函数的前缀和比较好计算，那么就可以简化计算过程。
　　像之前一样，试着计算一下$\sum_{i=1}^ng(i)$:

$$\sum_{i=1}^ng(i)=\sum_{i=1}^n\sum_{d|i}f(d)=\sum_{i=1}^n\sum_{d=1}^{\lfloor\frac{n}{d}\rfloor}f(d)$$ 　　而
$$\begin{aligned}\sum_{i=1}^ng(i)&=\sum_{i=1}^ni^2-3\sum_{i=1}^ni+2n=\frac{n(n+1)(2n+1)}{6}-\frac{3n(n+1)}{2}+2n\\&=\frac{n(n-1)(n-2)}{3}\end{aligned}$$ 　　step2同之前，就是换做考虑因数贡献的值$\sum_{i=1}^n\sum_{d|i}f(\frac{i}{d})=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)$。
　　这样$\sum_{i=1}^nf(i)=\frac{n(n-1)(n-2)}{3}-\sum_{i=2}^n\sum_{d=1}^{\lfloor\frac{n}{d}\rfloor}f(d)$。
　　预处理就用线筛和莫比乌斯反演 暴力枚举约数。（枚举到多少最适合我也不知道==不过$\sqrt n$其实挺小了。经过二分，发现确实是6e5比较好...）
　　Code.

BZOJ.3884.上帝与集合的正确用法 (扩展欧拉定理)

$Description$

　　给定p，
　　

$Solution$

　　欧拉定理：$若(a,p)=1$,则$a^b\equiv a^{b\%\varphi(p)}(mod\ p)$.
　　扩展欧拉定理：$a^b\equiv a^{b\%\varphi(p)+\varphi(p)}(mod\ p)$ (a为任意整数，b,p为正整数，且$b>\varphi(p)$（a,p不一定要互质）.证明.
　　指数是无穷的，但是模数是有限的，从不断减小p去考虑。
　　设$f(p)=2^{2^{2^{...}}}mod\ p$，次数是无穷的，所以肯定$>p$。根据扩展欧拉定理可得

$$\begin{aligned} f(p)&=2^{2^{2^{...}}mod \varphi(p)+\varphi(p)}(mod\ p)\\&=2^{f(\varphi(p))+\varphi(p)}(mod\ p)\end{aligned}$$
　　这样就有了f的递推式，可以直接递归计算。
　　那么复杂度是多少？
　　若$p$为偶数，则$\varphi(p)\leq\frac{p}{2}$；若$p$为奇数，则$\varphi(p)$为偶数，转化为偶数的情况。所以最多递归$log_2p$层。
　　$n>2时,\varphi(n)始终为偶数$的一个证明：
　　设$n=\prod p_i^{a_i}$，则$\varphi(n)=\prod (p_i^{a_i}-p_i^{a_i-1})$.
　　若$n=2^a,a\geq 2$，则$\varphi(n)=2^a-2^{a-1}=2^{a-1}(2-1)$，为偶数。
　　否则，若$n>2$，且至少有一个奇素数p，则$p_a-p_{a-1}(a\geq 1)$为偶数（因为两个数都是奇数）。
　　另官方题解.
　　Code.

51Nod.1237.最大公约数之和 V3(莫比乌斯反演 杜教筛 欧拉函数)

$Description$

　　$n\leq 10^{10}$，求

$$\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)\ mod\ (1e9+7)$$

$Solution$

　　首先

$$\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)=\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=d]$$
　　注意不是$\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=d]$！
$$\begin{aligned} \sum_{i=1}^n\sum_{j=1}^ngcd(i,j)&=\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=d]\\ &=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[gcd(i,j)=1]\\ &=\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(i)\lfloor\frac{n}{i}\rfloor\lfloor\frac{n}{i}\rfloor\\ &=\sum_{d=1}^nd\sum_{d|t,t\leq n}\mu(\frac{t}{d})(\lfloor\frac{n}{t}\rfloor)^2\\ &=\sum_{t=1}^n(\lfloor\frac{n}{t}\rfloor)^2\sum_{d|t}d\mu(\frac{t}{d})\\ &=\sum_{t=1}^n(\lfloor\frac{n}{t}\rfloor)^2\varphi(t) \end{aligned}$$
　　然后就可以杜教筛了。
　　最后一步用到 $$\sum_{d|n}\frac{n}{d}\mu(d)=\varphi(n)$$

证明：
　　首先有 $\sum_{d|n}\varphi(d)=n$（不证了）.
　　设 $f(n)=n$，则$f(n)=\sum_{d|n}\varphi(d)$.
　　那么 $\varphi(n)=\sum_{d|n}f(\frac{n}{d})\mu(d)$
　　即 $\sum_{d|n}\frac{n}{d}\mu(d)=\varphi(n)$.

　　Code.