0%

莫比乌斯反演通常用于解决求和内含$\gcd$的问题,通常是多个求和公式嵌套而成并且需要在线性的复杂度(甚至需要低于线性时间复杂度)内解决该问题。该博文就是来谈谈对莫比乌斯反演的理解。

Read more »

$$\sum_{i=1}^n \sum_{j=1}^m \frac{\mathrm{lcm}(i,j)}{\gcd(i,j)} \bmod 1000000~007$$

其中$1 \leq n, m \leq 10^7$。

Read more »

题目链接

欧拉函数$\phi(n)$被定义$1$~$n$中与$n$互质的数的个数。例如$\phi(5)=4$,因为$1$,$2$,$3$,$4$这四个数字与$5$互质。
定义$f$函数:$$f(n, k)=\sum\limits_{i=k}^{n-k}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor$$
给定$n$和$k$,其中$2\le n\le 10^{12}$,$1\le k\le min(\lfloor\frac{n}{i}\rfloor,1000000)$,求$f(n,k)$的值。

Read more »