4802: 欧拉函数
Description
Input
Output
Sample Input
Sample Output
当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质数检验方法：
直观想法我们直接取若干个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文章地址https://www.yii666.com/article/756191.html网址:yii666.com
（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)。文章来源地址:https://www.yii666.com/article/756191.html