本周总结 gcd与欧拉函数，容斥原理

gcd 与欧拉函数的结合存在一种划分的关系，具体如下，

这样划分与划分之前的交集为空，有了这样的关系后，一些题目则可以既能结合容斥原理又能结合欧拉函数，既可以用容斥原理来解决也可以用欧拉函数来解决。如果加上一些条件，某些数被选，某些数不被选，选之后的贡献为某一个值的方法有几个，则就又能牵扯到组合数。

在用容斥原理解题的过程中，往往要用到迭代法，在迭代的过程中最重要的是找清楚那一项应该被作为贡献加上，那一项应该被作为贡献减去，一般是和项数的奇偶性相关，如果在复杂一些，就是需要求出项数与加上减去之间的关系。这个找清楚了，题目也就清晰了。

中国剩余定理往往和循环次数相联系，和套圈相关，当然，也可以在套圈的过程中结合容斥原理，用容斥原理来找出圈的大小，即要模的数的大小，或者是取模后的结果有哪些。应该也可以和组合数结合，用组合数来找出循环节大小，或者用扩展欧几里得算出C(n,m)中n,m的大小来，这两者之前应该存在着这样的结合形式，还没遇到。

容斥原理不光能结合个数问题，还能和区域问题联系，一个区域的大小往往可以看成是有大小这个数的元素的集合，两个区域的交错即为相同的元素。

用了一天的时间把才把原根的相关模板搞的有点熟，越往后学，牵扯到的知识点越多，几乎要用到所有之前学过的知识，在看博客时无意间接触到了卡特兰数，才发现组合数大有学问，然后又发现自己把高中的杨辉三角形忘了个精光，几乎是啥也不会，步步是坑，慢慢填。哎，一入信竞深似海，从此数学是祖宗。江湖相忘不想念，相遇请君先入坑。
有关卡特兰数看到了一个很好的文章，贴一下
http://lanqi.org/skills/10939/

做题截图