数论习题 2018.4

数学，数论

---

代码见这.

BZOJ.2440.完全平方数

题意即求第$k$个无平方因子数。

无平方因子数(Square-Free Number)，即分解之后所有质因数的次数都为1的数

可以想到莫比乌斯函数，假设$n$是答案，那么有

$$k=n-\sum_{i=1}^n(1-|\mu(i)|)$$
（从这里能看出$x$的上界，后面的$\sum$肯定是$<\frac{n}{2}$的，所以$n\leq 2*k$）
二分一个$n$，求$[1,n]$中有多少个无平方因子数。
既然带着个平方就都开方。根据容斥，对于$[1,\sqrt{n}]$中的质数，答案为 $$[1,n]中0个质数平方倍数的个数-1个质数平方倍数的个数+2个质数平方倍数的个数-\ldots$$
即对于奇数个质数平方贡献为负，偶数个贡献为正；若存在某个质因子的次数$>1$，那么对答案没有影响(如$pi^2*pj^2$在计算$pi*pj$时统计了个数)。这也符合莫比乌斯函数的特点。那么答案可以写为： $$\sum_{i=1}^{\lfloor\sqrt{n}\rfloor}\mu(i)*\lfloor\frac{n}{i^2}\rfloor$$

BZOJ.2820.YY的GCD

$Description$
　　求

$$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)为质数]$$
$Solution$
$$\begin{aligned} Ans &=\sum_{i=1}^n\sum_{j=1}^m[(i,j)为质数]\\ &=\sum_{p}\sum_{i=1}^n\sum_{j=1}^m[(i,j)=p]\\ &=\sum_{p}\sum_{i=1}^{\lfloor{\frac{n}{p}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{p}}\rfloor}[(i,j)=1]\\ &=\sum_{p}\sum_{d=1}^{min(\lfloor{\frac{n}{p}}\rfloor,\lfloor{\frac{m}{p}}\rfloor)}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor \end{aligned}$$
　　带着$pd$不舒服啊，令$t=pd$，则
$$\begin{aligned} Ans &=\sum_{p}\sum_{d=1}^{min(\lfloor{\frac{n}{p}}\rfloor,\lfloor{\frac{m}{p}}\rfloor)}\mu(d)\lfloor\frac{n}{pd}\rfloor\lfloor\frac{m}{pd}\rfloor\\ &=\sum_p\sum_{p\mid t}\mu(\frac{t}{p})\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\\ &=\sum_{t=1}^{min(n,m)}\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\sum_{p\mid t}\mu(\frac{t}{p}) \end{aligned}$$
　　前面那部分好求，后面那部分如果能用前缀和求的话就容易了。事实上也是可以的。
　　令$F(t)=\sum_{p\mid t}\mu(\frac{t}{p})$，那么 $$Ans=\sum_{t=1}^{min(n,m)}F(t)\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor$$
　　对于每个$p$我们只需要暴力枚举约数$d$更新$F(pd)$就可以了。
　　复杂度(转自ppt by $popoqqq$)：由 $$\lim_{n\rightarrow\infty}\sum_{i=1}^n\frac{1}{i}=\ln n+r$$
　　易知，每个质数更新时是均摊$O(\log n)$的，而质数个数恰好为$O(\frac{n}{\log n})$，所以暴力枚举+维护前缀和的时间复杂度为$O(n)$。
　　计算复杂度自然就是$O(\sqrt{n})$了。
　　
　　另外$F(t)=\sum_{p\mid t}\mu(\frac{t}{p})$好像是可以一起线性筛出来的。参考。
$$F(p*k)= \begin{cases} \mu(k), & p\mid k\\ \mu(k)-F(k), & p\nmid k \end{cases}$$
　　对于这个式子，$F(p*k)=\sum_{p'\mid p*k}\mu(\frac{p*k}{p'})$

• $p\mid k$时，有$p*k$的因子$p$的次数$\geq 2$。
  　　1.$p'=p$时，即$\mu(k)$。
  　　2.$p'\neq p$时，因为$p$的次数$\geq 2$，所以为$0$。
  　　因此此时答案为$\mu(k)$。
• $p\nmid k$时，有$p*k$的质因子$p$的次数为$1$。
  　　1.$p'=p$时，也是$\mu(k)$。
  　　2.$p'\neq p$时，此时$p'$与$p$互质，由$\mu$的积性函数性质，可化为$\sum_{p'\mid k}\mu(\frac{k}{p'})\mu(p)$，$\mu(p)=-1$，所以为$-\sum_{p'\mid k}\mu(\frac{k}{p'})=-F(k)$。
  　　因此此时答案为$\mu(k)-F(k)$。
  　　注意对于每个质数$p$，$F(p)=1$；$F(1)=0$。
  　　

BZOJ.3529.数表

$Description$
　　令$F(i)$表示$i$的约数和，给定$n,m,a$，多次询问，求

$$\sum_{i=1,i\leq n}_{j=1,j\leq m}_{F(gcd(i,j))\leq a}F(gcd(i,j))\mod 2^{31}$$
$Solution$
　　$F(i)$是一个积性函数，根据约数和定理可以线性筛出来。（具体见这，好像比较麻烦，所以直接$O(n\log n)$求）

约数和定理：若$n=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$，则

$$F(n)=(p_1^0+p_1^1+p_1^2+\ldots+p_1^{a_1})(p_2^0+p_2^1+p_2^2+\ldots+p_2^{a_2})\ldots(p_k^0+p_k^1+p_k^2+\ldots+p_k^{a_k})$$

　　先考虑去掉$a$的限制，

$$\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=d]*F(d)$$
$$\sum_{d=1}^nF(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]$$
$$\sum_{d=1}^nF(d)\sum_{i=1}^{min}\mu(i)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor$$
　　令$T=id$，
$$\sum_{d=1}^nF(d)\sum_{d\mid T}\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$$
　　枚举$T$，把$\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$放前边，
$$\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d\mid T}F(d)\mu(\frac{T}{d})$$
　　前半部分显然可以优化到$O(\sqrt{n})$，对于后半部分和之前一样，暴力枚举约数更新，然后求遍前缀和，复杂度$O(n\log n)$。
　　然后是$a$的限制，因为只有$F(i)\leq a$的$i$才会对答案有贡献，所以我们将询问按$a$排序，$i$按$F(i)$排序，每次询问将所有$\leq a$的$F(i)$插入，用树状数组维护前缀和。
　　（详细写一下，原先对于每个$F(d)$，我们在预处理时要更新$d$的所有倍数的$\sum F*\mu$，然后前缀和。现在根据$F(d)$的大小依次更新$d$的倍数）
　　复杂度$O(n\log^2n+q\sqrt{n}\log n)$。

　　另外对于$2^k$取模相当于和$2^k-1$取"与(&)"。因此对于这题不需要取模，用int自然溢出然后最后答案对$2^{31}-1$取与即可。（参考这。并不是很懂。。）
　　注意如果$k$不是$31$的话，得到的结果应是同余的（即可能是负的）。

---

小结
套路1：由$\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=d]$，去枚举$d$，化简出$\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]$。

套路2：对于$\sum_{i=1}^{min}\mu(i)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor$，令$T=id$，得到$\sum_{d\mid T}\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$。

套路3：枚举$T$，把$\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$放前边，后面留下个$\sum_{d\mid T}^nF(d)\mu(\frac{T}{d})$。

反正都是满满的套路

---

BZOJ.4816.数字表格

　　这个好像简单些啊，只要不犯sb错误
$Description$
　　用$f[i]$表示$Fibonacci$数列的第$i$项，求

$$\prod_{i=1}^n\prod_{j=1}^mf[\gcd(i,j)]\mod (10^9+7)$$
$Solution$
$$\begin{aligned} Ans &=\prod_{i=1}^n\prod_{j=1}^mf[(i,j)]\\ &=\prod_{d=1}^n\prod_{i=1}^n\prod_{j=1}^m[(i,j)=d]*f[d]\\ &=\prod_{d=1}^nf[d]^{\sum_{i=1}^n\sum_{j=1}^m[(i,j)=d]}\\ &=\prod_{d=1}^nf[d]^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[(i,j)=1]}\\ &=\prod_{d=1}^nf[d]^{\sum_{i=1}^{min}\mu(i)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor}\\ &=\prod_{d=1}^nf[d]^{\sum_{d\mid T}\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor} \end{aligned}$$
　　直接去枚举$T$，
$$\begin{aligned} Ans &=\prod_{d=1}^nf[d]^{\sum_{d\mid T}\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}\\ &=\prod_{T=1}^n\prod_{d\mid T}f[d]^{\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}\\ &=\prod_{T=1}^n\prod_{d\mid T}(f[d]^{\mu(\frac{T}{d}) })^{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor} \end{aligned}$$
　　同之前，枚举约数暴力更新$\prod_{d\mid T}f[d]^{\mu(\frac{T}{d})}$，复杂度$O(n\log n)$。($\prod_{d\mid T}f[\frac{T}{d}]^{\mu(d)}$)
　　注意次幂不能直接取模，利用费马小定理可以对$mod-1$取模。
　　然后注意$f[0]=0$。。

小结：
套路1：把$\prod$换到幂上去，这样就有$\sum$了。

套路2：令$T=id$，在最外层枚举$T$。

另外常见的就不再写了。

.
.
.
.
.
.