BZOJ 4802 欧拉函数

4802: 欧拉函数

Description

已知N，求phi(N)

Input

正整数N。N<=10^18

Output

输出phi(N)

Sample Input

8

Sample Output

4

---

　　

　　很明显，这样的题就是一道十分简单的入门题。只是N比较大，但输入和输出都还没有爆long long。如果输入高精度数，那

就很恶心了（虽然可以定义大整数类Big Int）。

　　phi[n]=n∏(1-(1/p))，所以是Miller-Rabin和Pollard-Rho算法，用来分解一个大数的质因子。

　　当n较小的时候，若要算出所有的phi(i)，那么欧拉筛明显是最优的，线性空间线性时间。

　　若只需算出固定n对应的前缀和∑phi(i)，那很明显，不必算出所有的phi(i)。

　　对于这种前缀和∑f(i)的计算，若使用杜教“筛”（这并不是素数筛），需要构造一个h=f*g(*指狄利克雷卷积)，且前缀和∑g(i)与前缀和∑h(i)可以十分方便地算出。然后经过一系列较为方便的演算，做到大事化小递归求解。如果预先打表O（n^(2/3)），此时复杂度最优为O（n^(2/3)）。

　　我们可以发现，杜教筛对f的要求很苛刻。但是，洲阁筛使用了完全不同的思路。只要f(i)是多项式的，那么我们可以想到类似DP的方法。这样原始是O（n^(3/2)）即O(n*sqrt(n))的，但通过各种优化可以压至O(n^(3/4)/log n)的级别。

　　最后，说一下此题的方法。

　　摘自：http://www.cnblogs.com/galaxies/p/bzoj4802.html

• Miller-Rabin质数检验方法：

　　　　根据费马小定理，如果p是素数，a<p，那么有a^(p-1) mod p = 1。

　　　　直观想法我们直接取若干个a，如果都有一个不满足，那么p就是合数。

　　　　遗憾的是，存在Carmichael数：你无论取多少个a，有一个不满足，算我输。

　　　　比如：561 = 11*51就是一个Carmichael数。

　　　　

　　　　那么，额。。所以我们需要改进算法。

　　　　首先有：如果p是素数，x是小于p的正整数，且x^2 mod p = 1，那么要么x=1，要么x=p-1

　　　　（这个废话，x=p-1模意义下等于x=-1）

　　　　然后我们可以展示下341满足2^340 mod 341 = 1，却不是素数（341=31*11）的原因：

　　　　　　2^340 mod 341 = 1

　　　　　　2^170 mod 341 = 1

　　　　　　2^85 mod 341 = 32

　　　　　　（32这个数很那啥啊怎么不等于340也不等于1啊。。这明显有内幕嘛32*32=1024,1024=341*3+1）

　　　　那么就能说明这个数不是素数。

　　　　如果是素数，一定是从p-1变到1，或是把所有2的次幂去除完，本来就等于1（这样平方完就一直是1了）

　　　　所以要么把所有2的次幂去除完，本来就等于1，要么存在某一个次幂=p-1（这样就正常多了）

　　　　这就是Miller-Rabin素数验证的二次探测。

　　　　应该来说Miller-Rabin算法也是挺好写的

　　　　其中mul(a,b,c)表示a*b%c（因为a*b会爆longlong，所以用快速加）

• 好了下一个是Pollard-Rho算法：

  如果现在拆分的是n：Pollard-Rho(n)

  主要流程：Miller-Rabin判断是否质数，是返回，否就试图找出其中一个因子d，然后递归做Pollard-Rho(d)和Pollard-Rho(n/d)。