标签: 莫比乌斯反演

5 篇文章

P3327 [SDOI2015]约数个数和
Description 题目链接:P3327 设 $d(x)$ 表示 $x$ 的约数个数,有 $T$ 组数据,给定 $n,m$ 求 $$\sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)$$ $1\leq T,n,m\leq 5\times 10^4$ Solution 首先你得知道: $$d(ij)=\sum\…
P2257 YY的GCD
Description 题目链接:P2557 有 $T$ 组数据,求: $$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)\in prime]$$ $T\leq 10^4,n,m\leq 10^7$ Solution 显然可以枚举质数,所以原式可以化为: $$\sum\limits_{i=1}^n\s…
P2522 [HAOI2011]Problem b
Description 题目链接:P2522 有 $T$ 组数据,求 $$\sum\limits_{i=x}^n\sum\limits_{j=y}^m[gcd(i,j)=k]$$ $1\leq T,x,y,n,m,k\leq 5\times 10 ^4$。 Solution 可以根据容斥原理,原式可以分成四个子问题,每个子问题的式子为: $$\su…
浅谈莫比乌斯反演
浅谈莫比乌斯反演 那些各种各样的性质与定理,大多是前人几年甚至几十年才得出来的,哪里是你几天就能理解并证明的。 简介 莫比乌斯反演是数论中的重要内容。对于一些函数 $f(n)$,如果很难直接求出它的值,而容易求出其倍数和或约数和 $g(n)$,那么可以通过莫比乌斯反演简化运算,求得 $f(n)$ 的值。--OI Wiki 莫比乌斯函数 定义 $$\…