数论攻克

引子

前天打了南京站的网络赛，南航杀我，有一道叫super_log的题，题目要求算出幂塔函数共 b 个 a 乘幂的结果模 m 的值。

虽然我当时不会手码快速幂，但是板子还是有的，于是我把取模的快速幂放上去，递归快速幂一串后发现（妈妈我递归没错了！），最后一个样例算出的是126。

不对，可能是因为我的指数取模了所以结果不对了，于是我直属放弃了递归，在最后就快速幂取模一次，样例通过了。

开心，提交，不出所料，TLE。

之后就对1900ms优化到1000ms束手无策了??。

于是我看了题解，题解大人是这么写的：

　　　　由于指数会非常大，使用欧拉定理递归降幂即可。需要特判一下 a 与 m 不互质的情况。 欧拉函数很快会迭代到 ，可以提前退出，速度很快。

我这才发现原来我做不出的原来以前都学过，哭了，数论嘛，我重新学好了吧，欧拉方程和欧拉定理、欧拉公式不同好了好了我知道了，那么我们开始吧！

OPEN

第一步我们从ppt开始吧（对不起师哥我一定学会！）

1. 自然数分为质数和合数，对于质数的判断：

Code

1 bool is_prime(int n)
2 {
3     if (n % 6 != 1 && n % 6 != 5)return false;
4     for (size_t i = 5; i < (int)sqrt(n) + 1; i += 6)
5     {
6         if (n % x == 0 || n % (x + 2) == 0) return false;
7     }
8     return true;
9 }

is_prime

2. 因子分解定理

对于任意一个正整数，一定可以被唯一分解为若干个质数的乘积的形式：

　　　　n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k

其中，p_i 是n的质因子，a_i 是p_i 的个数。

因子分解过程：从2到sqrt(n)枚举因子 k ，判断n是否可以被k整除。在整个过程中，每找到n的因子，将n /= k，

使对应的枚举上限因此变小。因此对于合数复杂度<O(sqrt(n))，而质数最坏为O(sqrt(n))，可以通过预先打好质数表，如果n为质数则跳出。

Code

（普通正整数的因子分解）（此代码不包含质数表）（返回的num值为存储质因子的真实大小）

 1 const int maxn = 1e5 + 10;
 2 int cnt[maxn];
 3 int fac[maxn];
 4 int getFac(int n)
 5 {
 6     int num = 0, sum = 0, m = sqrt(n + 0.5);
 7     for (int k = 2; k <= m; k++)
 8     {
 9         sum = 0;
10         while (n % k == 0)
11         {
12             n /= k;
13             sum++;
14         }
15         if (sum != 0)
16         {
17             fac[num] = k;
18             cnt[num++] = sum;
19         }
20         m = sqrt(n + 0.5);
21     }
22     if (n != 1)
23     {
24         fac[num] = n;
25         cnt[num++] = 1;
26     }
27     return num;
28 }

getFactor

因子个数D：正整数n的所有不同因子的总个数，计算公式：

　　　　D = (a₁+1) × (a₂+1) × ... × (a_k+1)

证明：组合数学的方法

因子求和S：正整数n的所有不同因子的总和，计算公式：

　　　　S = Π[ 1 + p_i + p_i² + … + p_i^a_i ] = Π[ (p_i^(a_i+1) - 1)/(p_i-1) ]

证明：多项式乘法的展开式

Example

12的因子有1、2、3、4、6、12，总计6个，所有因子和S=1+2+3+4+6+12=28

分解质因子得到12=2² x 3¹，代入公式因子个数D=(2+1)x(1+1)=6，所有因子和S=(1+2+4) x (1+3) = 28

阶乘的因子分解（：给定正整数n，分别求n! 的因子分解式中质因子p_i 的数量a_i ，计算公式：

　　　　S(p) = Σ[ n/p + n/(p²) + n/(p³) + … + n/(p^k) ]

其中p^k <=n，时间复杂度为O(log(n))，只需要枚举质因子，然后分别按照上述方式分解即可

-》洛谷P2043：当时没看到这里，直接求出阶乘后再用（Code：getFactor）去求，结果97! 比long long还长直接爆了，还是入门题，哭了orz

应用：求n!的末尾有多少个零

思路：考虑求n!的因子分解式中有多少个2和5

2. 最大公因数 && 最小公倍数

数论攻克

原文：https://www.cnblogs.com/xzmxiao/p/11456505.html