文章

BZOJ-1042 [HAOI2008]硬币购物

背包 DP + 容斥原理

假设班里有

    $math_inline$10$math_inline$

个学生喜欢数学，

    $math_inline$15$math_inline$

个学生喜欢语文，

    $math_inline$21$math_inline$

个学生喜欢编程，班里至少喜欢一门学科的有多少个学生呢？

给定任意正整数

    $math_inline$n$math_inline$

，那么在小于等于

    $math_inline$n$math_inline$

的所有正整数之中，有多少个与

    $math_inline$n$math_inline$

构成互质关系？

计算这个值的方法就叫做欧拉函数

    $math_inline$\phi(n)$math_inline$

表示：在

    $math_inline$1$math_inline$

到

    $math_inline$n$math_inline$

之中，与n构成互质关系的数的数量。

莫比乌斯反演是数论中的重要内容，对于一些函数

    $math_inline$f(n)$math_inline$

，如果很难直接求出它的值，而容易求出其倍数和或约数和

    $math_inline$g(n)$math_inline$

，那么可以通过莫比乌斯反演简化运算，求得

    $math_inline$f(n)$math_inline$

的值。

开始学习莫比乌斯反演前我们需要一些前置知识：积性函数、Dirichlet卷积、莫比乌斯函数

• 威尔逊定理
• 欧拉定理（数论中的欧拉定理）
• 中国剩余定理（又称孙子定理）
• 费马小定理

• 乘法逆元