组合数学 - 预备材料

未分类

。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。。。。。
。。。。
。。。。
。。。。
。。。。
。。。。
以下涉及的两个练习题均可在CJOJ提交。

莫比乌斯函数的介绍

P2396 - 完全平方数

小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。
这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？
本题有多组数据，1 ≤ Ki ≤ 10^9， T ≤ 50

分析

首先我们可以二分答案x，那么问题便转化成统计1-x中间有多少个数不是完全平方数。我们可以使用类似筛法的方法，把是完全平方数的数减掉。根据容斥原理，所有数-1个质因子的平方的倍数+2个质因子的平方的倍数-3个质因子的平方的倍数...就是最终的答案。
枚举每一个可能的平方因子$x^2$，如果 $x$ 只有奇数个质因子，那么要减去它的倍数，如果它有偶数个质因子，那么要加上它的倍数。如果它的某一质因子出现了两次及以上，那么就可以忽略它。
请仔细思考上述算法的正确性。

线性筛法

之前我们一直使用的是nlogn筛法求质数，但是注意到在筛的过程中，一个质数被反复标记，造成了不必要的计算，因此我们可以尝试对这个算法进行改进。

P2395 - 思维的强者

思维的强者给你布置了一道预备练习题。
你需要完成以下三个操作：
1，对于给定的n，输出第n个质数。
2，对于给定的n，输出 $\mu(n)$。
3，对于给定的n，输出 $\phi(n)$。
n<=$10^7$

输入

一个行一个整数T，代表询问总数。
之后对于每组询问，有一行两个整数op和n，分别对应操作序号和上面的n。

输出

对于每组询问，输出一行答案。

样例

输入：

3
1 1
2 1
3 1

输出：

2
-1
1

分析

你可以参考下面的线性筛代码以了解线性筛的原理：

void sieve(){
    mu[1]=1;
    for(int i=2;i<maxn;i++){
        if(!vis[i]){ mu[i]=-1;prime[++pnt]=i; }
        for(int j=1;j<=pnt && i*prime[j]<maxn;j++){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }//这样可以保证每个数只被筛出一次，你可以背下来或者慢慢理解
            else{
                mu[i*prime[j]]=-mu[i];
            }
        }
    }
}

你可以手玩、使用gdb调试或者搜索相关博客来加深理解。
请注意，上面的函数并没有筛出$\phi(x)$，你需要根据自己的理解补充相关的代码。
如果你暂时不理解莫比乌斯函数也没关系，你只需要补充筛欧拉函数的代码即可。