5.1 简单数学

（1）B1019 & A1069

给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的 6174，这个神奇的数字也叫 Kaprekar 常数。
例如，我们从6767开始，将得到
7766 - 6677 = 1089 9810 - 0189 = 9621 9621 - 1269 = 8352 8532 - 2358 = 6174 7641 - 1467 = 6174 … …
现给定任意 4 位正整数，请编写程序演示到达黑洞的过程。

输入格式：

输入给出一个 (0,104) 区间内的正整数 N。

输出格式：

如果 N 的 4 位数字全相等，则在一行内输出 N - N = 0000；否则将计算的每一步在一行内输出，直到 6174 作为差出现，输出格式见样例。注意每个数字按 4 位数格式输出。

输入样例 1：

6767

输出样例 1：

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174

输入样例 2：

2222

输出样例 2：

2222 - 2222 = 0000

题解：

（1）输出格式的控制，如：高位补0等，不需要单独写函数，printf里面直接%04d就OK了
**单独涉及函数将int转化为数组，再设计一个函数将数组转换为int数字。因为做减法需要是数，但是排序需要是数组，因此需要int与array的相互转化
（3）sort默认从小到大，第三个参数省略即可。降序排列需要写cmp函数
ps: 对结构体数组排序，调用ｓｏｒｔ时必须写ｃｍｐ函数，否则会因为不知道对结构体内哪个元素排序而ERROR

代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4. int n,num[4];
  5. bool cmp (int a,int b)
  6. {
  7.     return a>b;
  8. }
  9. void to_array(int n,int num[])
  10. {
  11.     int k=1000;
  12.     for(int i=0;i<4;++i){
  13.         num[i] = n/k;
  14.         n = n%k;
  15.         k/=10;
  16.     }
  17. }
  18. int to_num (int num[])
  19. {
  20.     int sum=0;
  21.     sum = num[3] + num[2]*10 + num[1]*100 + num[0]*1000;
  22.     return sum;
  23. }
  24. int main()
  25. {
  26.     scanf("%d",&n);
  27.     int MAX,MIN;
  28.     while (1)
  29.     {
  30.         int result;
  31.         to_array(n,num);
  32.         sort(num,num+4);
  33.         MIN = to_num(num);
  34.         sort(num,num+4, cmp);
  35.         MAX = to_num(num);
  36.         n = MAX-MIN;
  37.         printf("%04d - %04d = %04d\n",MAX,MIN,n);
  38.         if(n==0||n==6174){
  39.             break;
  40.         }
  41.     }
  42.     return 0;
  43. }

5.2 GCD & LCM

GCD:

定理：设a,b均为正整数，则gcd(a,b) = gcd(b,a%b)

Therefore:
递归式： gcd(a,b) = gcd(b,a%b)
递归边界：gcd(a,0) = a

  1. int gcd (int a,int b)
  2. {
  3.     if(b==0){
  4.         return a;
  5.     }
  6.     else return gcd(b,a%b);
  7. }

LCM:

定理：正整数a,b的最大公约数为d，则最小公倍数为a*b/d. (通过画韦恩图很好理解)

Example:

题目描述

一组正整数的最小公倍数 （LCM） 是可被集合中的所有数字整除的最小正整数。例如，5、7 和 15 的 LCM 为 105。

输入

输入将包含多个问题实例。输入的第一行将包含一个整数，指示问题实例的数量。每个实例将由一行形式为 m n1 n2 n3 …nm，其中 m 是集合中的整数数，n1 …nm 是整数。所有整数都将为正数，并且位于 32 位整数的范围内。

输出

对于每个问题实例，输出一行，其中包含相应的 LCM。所有结果都将位于 32 位整数的范围内。

样例输入

2
2 3 5
3 4 6 12

样例输出

15
12

题解：

  1. **简单题，没啥说的，但是注意一下数据类型，long long,scanf和printf时注意一下是%lld**
  1. #include <cstdio>
  2. int gcd (long long a,long long b)
  3. {
  4.     if(b==0){
  5.         return a;
  6.     }
  7.     else return gcd(b,a%b);
  8. }
  9. long long lcm (long long a,long long b)
  10. {
  11.     return (a*b)/gcd(a,b);
  12. }
  13. int main()
  14. {
  15.     int n;
  16.     scanf("%d",&n);
  17.     for(int i=0;i<n;++i)
  18.     {
  19.         int m;
  20.         scanf("%d",&m);
  21.         long long ans[m];
  22.         for(int j=0;j<m;++j)
  23.         {
  24.             scanf("%lld",&ans[j]);
  25.         }
  26.         for(int p=0;p<=m-2;++p){
  27.             ans[p+1] = lcm(ans[p],ans[p+1]);
  28.         }
  29.         printf("%lld\n",ans[m-1]);
  30.     }
  31.     return 0;
  32. }

5.3 分数的四则运算

5.3.1 分数的表示与化简

存储分数主要是储存分子和分母，因此，我们通常用结构体来存储。

  1. struct Fraction{
  2.     int up, down;
  3. };

image.png

  1. Fraction reduction (Fraction result)
  2. {
  3.     if(result.down < 0){
  4.         result.up = -result.up;
  5.         result.down = -result.down;
  6.     }
  7.     if(result.up==0){
  8.         result.down = 1;
  9.     }else{
  10.         int d = gcd(abs(result.up), abs(result.down));
  11.         result.up /= d;
  12.         result.down /= d;
  13.     }
  14.     return result;
  15. }

5.3.2 分数的四则运算

  1.  ![image.png](https://cdn.nlark.com/yuque/0/2022/png/22209759/1643345476630-6c81419f-7d40-4b37-ab1c-30c6b895c2ab.png#clientId=u2d0403b6-0951-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=153&id=ufae9ed4b&margin=%5Bobject%20Object%5D&name=image.png&originHeight=209&originWidth=867&originalType=binary&ratio=1&rotation=0&showTitle=false&size=159730&status=done&style=none&taskId=u51e8c1ae-95e0-4111-a173-f34109c701b&title=&width=633.6000366210938)<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/22209759/1643345438192-6fed06c1-1cf7-441d-96fa-f34541427b7f.png#clientId=u2d0403b6-0951-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=865&id=ub0cb85eb&margin=%5Bobject%20Object%5D&name=image.png&originHeight=850&originWidth=555&originalType=binary&ratio=1&rotation=0&showTitle=false&size=480725&status=done&style=none&taskId=u74d0839c-bcdd-4ec8-9ac9-f8da0cc31e0&title=&width=565)<br />**【特判】注意：分数的除法需要注意，当除数为0时，即f2.up为0时，需要输出错误信息（自定义），只有当除数不为0时才能用上面的公式。**

5.3.3 分数的输出

image.png

  1. void showResult (Fraction r)   // 输出分数r
  2. {
  3.     r = reduction(r);
  4.     if(r.down == 1){
  5.         printf("%lld",r.up);
  6.     }
  7.     else if(abs(r.up)>r.down){     //假分数
  8.         //r.down不用abs，因为在分数构建时，我们就判断了当分母为0时，分子分母同时取相反数
  9.         printf("%d %d/%d",r.up/r.down, abs(r.up)%r.down,r.down);
  10.     }else{   // 不是上面两种情况就是真分数
  11.         printf("%d/%d",r.up,r.down);
  12.     }
  13. }
  1.   **注意：正常情况下，分数的乘法和除法可能会使分子或者分母超过int范围，因此其实我们一般使用long long数据类型来存储。**

5.4 素数

5.4.1 素数的判断

有约数一定是成对出现，也就是一个>sqrt(n)，一个<sqrt(n)，因此只需要遍历从2~sqrt(n)即可。

  1. bool isPrime (int n)
  2. {
  3.     if (n<=1){
  4.         return false;
  5.     }
  6.     for(int i=2;i<= sqrt(n);++i){
  7.         if(n%i==0){
  8.             return false;
  9.         }
  10.     }
  11.     return true;
  12. }

如果for循环括号里的的判断条件是 i*i<=n，在数据较小时没问题，但是怕相乘后超过int范围。

5.4.2 素数表

  1.   **如果我们用上面的方法来判断一个数是否为素数，那么列举前n个正整数的素数的复杂度就是O(n*sqrt(n))，数据量在10****5****量级以下是没有问题的。但是超过10****5****就不容乐观了。因此，我们通常采用下面的这种素数筛的方法，复杂度降为O(nlognlogn)**<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/22209759/1643422442187-0f6b5a1f-c548-49b4-afc7-e0443c4e4051.png#clientId=u5a0e5ee9-7646-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=712&id=u7d4db437&margin=%5Bobject%20Object%5D&name=image.png&originHeight=840&originWidth=731&originalType=binary&ratio=1&rotation=0&showTitle=false&size=765461&status=done&style=none&taskId=u3a580430-96a2-4a7d-80ec-21744cd4002&title=&width=619.7999877929688)
  1. // P163 埃氏筛法
  2. #include <cstdio>
  3. const int maxn = 100;
  4. int prime[maxn+1];
  5. bool p[maxn+1]={false};
  6. int num = 0;
  7. void Find_Prime()
  8. {
  9.     for(int i=2;i<=maxn;++i)
  10.     {
  11.         if(!p[i]){
  12.             prime[num++] = i;
  13.             for(int j=i+i;j<=maxn;j+=i){
  14.                 p[j] = true;
  15.             }
  16.         }
  17.     }
  18. }
  19. int main()
  20. {
  21.     Find_Prime();
  22.     for(int i=0;i<num;++i){
  23.         printf("%d ",prime[i]);
  24.     }
  25.     return 0;
  26. }
  1. **ps: 第二个for循环的第三个参数是 j+=i ，不能写成 j+i 。 （++j 其实就等价于 j+=1）**

(1) B1013

令 Pi 表示第 i 个素数。现任给两个正整数 M≤N≤104，请输出 PM 到 PN 的所有素数。

输入格式：

输入在一行中给出 M 和 N，其间以空格分隔。

输出格式：

输出从 PM 到 PN 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

输入样例：

5 27

输出样例：

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

题解：

注意：
（1）格式控制，行末不能有多余空格！
（2） 建议代码修改：函数里加上if(num>=n) break; 降低复杂度，因为只需要找到前n个素数即可
（3） maxn不能设为10000，因为n的上限是10000，前10000个素数的上限不可能是10000.n是前n个素数，是输入的第二个。

  1. #include <cstdio>
  2. const int maxn = 10000000;
  3. int Prime[maxn];
  4. bool p[maxn+1] = {false};
  5. int num=0,cnt=0;
  6. void Find_Prime ()
  7. {
  8.     for(int i=2;i<=maxn;++i)
  9.     {
  10.         if(!p[i]){
  11.             Prime[num++] = i;
  12.             for(int j=i+i;j<=maxn;j+=i){
  13.                 p[j] = true;
  14.             }
  15.         }
  16.     }
  17. }
  18. int main()
  19. {
  20.     Find_Prime();
  21.     int m,n;
  22.     scanf("%d%d",&m,&n);
  23.     for(int i=m-1;i<=n-1;++i){
  24.         if(cnt%10==0 && cnt!=0){
  25.             printf("\n");
  26.         }
  27.         if((cnt-9)%10==0 || i==n-1)
  28.             printf("%d",Prime[i]);
  29.         else
  30.             printf("%d ",Prime[i]);
  31.         ++cnt;
  32.     }
  33.     return 0;
  34. }

5.5 质因子分解

  1.  **由于每个质因子都可以不止出现一次，因此不妨定义结构体factor，用来存放质因子及其个数，如下：**
  1. struct factor{   //x为质因子，cnt为其个数
  2.     int x;
  3.     int cnt;
  4. }fac[10];
  1.  **考虑到2×3×5×7×11×13×17×19×23×29就已经超过了int范围，因此对一个int型范围的数来说，fac数组的大小只需要开到10就可以了。**<br />**    如果p是n的质因子，那么给fac数组增加质因子p，并初始化其个数为0.然后只要p还是n的质因子，就让n不断的除以p，每次操作令P的个数++，直到p不再是n的因子为止。(如果p不是n的因子，就直接跳过)。**
  1.     if(n%Prime[i]==0){   //如果Prime[i]这个质数是n的因子
  2.         fac[num].x = Prime[i];    //记录该因子
  3.         fac[num].cnt = 0;
  4.         while (n%Prime[i]==0){   //计算出质因子Prime[i]的个数
  5.             fac[num].cnt++;
  6.             n /= Prime[i];
  7.         }
  8.         num++;    // 不同质因数个数++
  9.     }
  1. **如果在上面步骤结束后n仍然>1，说明n有且仅有1个大于sqrt(n)的质因子（有可能是n本身），这时需要把这个质因子加入fac数组，并令其个数为1.**

（1) A1059

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p_1_k_1×_p_2_k_2×⋯×_pmkm.

Input Specification:

Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification:

Factor N in the format N = p_1^_k_1_p_2^_k_2…*_pm^km, where pi‘s are prime factors of N in increasing order, and the exponent ki is the number of pi — hence when there is only one pi, ki is 1 and must NOT be printed out.

Sample Input:

97532468

Sample Output:

97532468=2^211171011291

题解：(代码注释有问号不懂)

（1）不放心可以把maxn开大一些（题目说int 范围内正整数进行质因子分解，因此素数开到10**5**应该可以）
（2）别忘记输入为1的时候的特判
（3）main函数里面别忘了调用Find_Prime
（4）下面的maxn写成n不是不行，但是在之前忽略了主函数的出现顺序，之前是先调用，再scanf，所以n在这里永远是0。倒是输出结果永远是blablabla = blablabla (没分解，其实是因为素数表里啥也没有)
image.png

代码：

  1. #include <cstdio>
  2. #include <cmath>
  3. const int maxn = 100010;
  4. bool P[maxn] = {false};
  5. int num=0;
  6. int Prime[maxn] = {0};
  7. int n;  //输入
  8. bool isPrime (int n)
  9. {
  10.     if(n==1){
  11.         return false;
  12.     }
  13.     for(int i=2;i<= sqrt(n);++i)
  14.     {
  15.         if(n % i == 0){
  16.             return false;
  17.         }
  18.     }
  19.     return true;
  20. }
  21. int pNum=0;  // pNum是前n个数有几个素数
  22. void Find_Prime()  // 求素数表
  23. {
  24.     for(int i=1;i<maxn;++i){
  25.         if(isPrime(i)){
  26.             Prime[pNum++] = i;
  27.         }
  28.     }
  29. }
  30. struct factor{  // x是质因子，cnt是其个数
  31.     int x;
  32.     int cnt;
  33. }fac[100];
  34. int main()
  35. {
  36.     Find_Prime();
  37.     scanf("%d",&n);
  38.     if(n==1){
  39.         printf("1=1");
  40.     }
  41.     else{
  42.         printf("%d=",n);
  43.         for(int i=0 ; i<pNum && Prime[i]<=sqrt(n) ; ++i)
  44.         {
  45.             if(n % Prime[i] == 0){
  46.                 fac[num].x = Prime[i];
  47.                 fac[num].cnt = 0;
  48.                 while (n % Prime[i] == 0){
  49.                     fac[num].cnt++;
  50.                     n = n/Prime[i];
  51.                 }
  52.                 num++;
  53.             }
  54.             if(n==1)  break;   //及时推出，节省时间
  55.         }
  56.         if(n!=1){
  57.             fac[num].x = n;    //????????????????
  58.             fac[num++].cnt = 1;
  59.         }
  60.         // 按格式输出结果
  61.         for(int j=0;j<num;++j){
  62.             if(j>0){
  63.                 printf("*");
  64.             }
  65.             printf("%d",fac[j].x);
  66.             if(fac[j].cnt>1){
  67.                 printf("^%d",fac[j].cnt);
  68.             }
  69.         }
  70.     }
  71.     return 0;
  72. }

附加知识点：

image.png

5.6 大整数运算

顾名思义，大整数运算肯定不是我们平时见到的整数，平时整数的运算直接printf就好了，但是大整数指超过int范围的整数，甚至可能是1000位，那我们如何运算呢？ 要想进行运算首先应该研究如何进行存储。

5.6.1 大整数的存储(a[1000]是高位，a[0]是低位)

把整数按字符换读入，然后存到数组中。而为了方便随时获取大整数的长度，一般定义一个int型变量len来记录其长度，并和d数组组合成结构体,一般地，定义完需要初始化，防止忘记，我们通常使用构造函数初始化（函数名和结构体名相同，无返回值）：

  1. struct bign{
  2.     int d[1000];
  3.     int len;
  4.     bign(){
  5.         memset(d,0,sizeof (d));
  6.         len = 0;
  7.     }
  8. };
  1.   **由于char数组读入时，整数的高位会变成数组的低位，整数的低位会变成数组的高位，因此需要让字符串倒着赋给d[ ] 数组：**
  1. bign change (char str[])    // 将整数转换为bign
  2. {
  3.     bign a;
  4.     a.len = strlen(str);      // bign的长度就是字符串的长度
  5.     for(int i=0;i<a.len;++i){
  6.         a.d[i] = str[a.len-i-1] - '0';  //逆着赋值
  7.     }
  8.     return a;
  9. }
  1. **如果需要比较两个bign的大小关系，先比len，len相同就从高位到低位依次比较：**
  1. int compare (bign a, bign b)  // 返回1->a大，-1->a小，0->一样大
  2. {
  3.     if(a.len>b.len)
  4.         return 1;
  5.     else if(a.len<b.len)
  6.         return -1;
  7.     else{
  8.         for(int i=a.len-1;i>=0;--i){
  9.             if(a.d[i]>b.d[i])
  10.                 return 1;
  11.             else if(a.d[i]<b.d[i])
  12.                 return -1;
  13.         }
  14.         return 0;    // 两数相等
  15.     }
  16. }

5.6.2 大整数的四则运算

5.6.2.1 加法

和普通的加法运算一样，和半加器也类似，看代码吧：

  1. bign add (bign a, bign b)
  2. {
  3.     bign c;
  4.     int carry = 0;   //carry是进位
  5.     for(int i = 0; i < a.len || i<b.len; ++i){
  6.         int temp = a.d[i] + b.d[i] + carry;
  7.         c.d[c.len++] = temp%10;  // 个位数为该结果
  8.         carry = temp/10;        // 十位数为新的进位
  9.     }
  10.     if (carry!=0){    // 退出循环时，a和b都没有数了，此时若进位不为0，则直接赋给最高位
  11.         c.d[c.len++] = carry;
  12.     }
  13.     return c;
  14. }

可运行的完整代码如下：

  1. #include <cstdio>
  2. #include <cstring>
  3. struct bign{
  4.     int d[1000];
  5.     int len;
  6.     bign(){
  7.         memset(d,0,sizeof (d));
  8.         len = 0;
  9.     }
  10. };
  11. bign change (char str[])
  12. {
  13.     bign a;
  14.     a.len = strlen(str);
  15.     for(int i=0;i<a.len;++i){
  16.         a.d[i] = str[a.len-i-1] - '0';
  17.     }
  18.     return a;
  19. }
  20. bign add (bign a, bign b)
  21. {
  22.     bign c;
  23.     int carry;
  24.     for(int i = 0; i < a.len || i < b.len; ++i){
  25.         int temp = a.d[i] + b.d[i] + carry;
  26.         c.d[c.len++] = temp % 10;
  27.         carry = temp/10;
  28.     }
  29.     if(carry != 0){
  30.         c.d[c.len++] = carry;
  31.     }
  32.     return c;
  33. }
  34. void print (bign a){
  35.     for(int i = a.len-1; i >= 0; --i){
  36.         printf("%d",a.d[i]);
  37.     }
  38. }
  39. int main()
  40. {
  41.     bign a,b,c;
  42.     char aa[1000];
  43.     char bb[1000];
  44.     scanf("%s%s",aa,bb);
  45.     a = change(aa);
  46.     b = change(bb);
  47.     c = add(a,b);
  48.     print(c);
  49.     return 0;
  50. }

注意：为了运算时代码方便，我们将数组中索引较大的元素存储成高位，较小的元素存储成低位（change函数逆序存储）。因此输出时（print函数）应从a.len-1开始 ！！

5.6.2.2 减法

和普通的减法运算一样，看代码吧：

  1. bign sub (bign a, bign b)  // 我觉得默认a>b，如果你知道谁大，可以调用上面的compare函数
  2. {
  3.     bign c;
  4.     for (int i=0; i < a.len || i < b.len; ++i)
  5.     {
  6.         if(a.d[i] < b.d[i]){   // 向索引下一位（高位）的元素借位
  7.             a.d[i+1]--;
  8.             a.d[i] += 10
  9.         }
  10.         c.d[i] = a.d[i] - b.d[i];
  11.     }
  12.     // 接下来，去掉最高位的0，同时至少保留一位最低位
  13.     while (c.len >= 2 && c.d[c.len-1] == 0){
  14.         c.len--;   
  15.     }
  16.     return c;
  17. }
  1. **有一点需要注意一下，按位减完之后，可能高位有几个0，因此，输出时去掉高位的0，上面的while循环就是这个作用。但是，不能直接从最高位依次去掉0，因为假如结果就是0，去掉0之后就啥也输出不出来了。**

5.6.2.3 高精度（bign）与低精度(int)的乘法

image.png

  1. bign multi (bign a, int b)
  2. {
  3.     bign c;
  4.     int carry = 0;   // 要赋初值0，看看循环体就懂了
  5.     for (int i = 0; i < a.len; ++i){
  6.         int temp = a.d[i] * b + carry;
  7.         c.d[c.len++] = temp % 10;  // 个位作为该位的结果
  8.         carry = temp / 10;  //高位部分作为新的进位
  9.     }
  10.     while (carry != 0){
  11.         c.d[c.len++] = carry % 10;
  12.         carry /= 10;
  13.     }
  14.     return c;
  15. }

注意：和加法不一样，加法最高位的进位最多是一位，而乘法的进位可能不是一位数，因此用while做判断。

5.6.2.4 高精度（bign）与低精度（int）的除法

image.png

  1. bign divide (bign a, int b, int &r)  //r为余数
  2. {
  3.     bign c;
  4.     c.len = a.len;
  5.     for(int i = a.len - 1; i >= 0; --i)
  6.     {
  7.         r = r * 10 + a.d[i];
  8.         if(r < b){
  9.             c.d[i] = 0;
  10.             r = r % b;
  11.         }
  12.         else{
  13.             c.d[i] = r / b;   // 商
  14.             r = r % b; //获得新的余数
  15.         }
  16.     }
  17.     while (c.len >= 2 && c.d[c.len-1] == 0){
  18.         c.len--;  // 和加法一样，去掉最高位的0，但是至少保留一位最低位
  19.     }
  20.     return c;
  21. }

注意：
（1） c.len = a.len ,因为根据原理，商和高精度数是一一对应的，只是可能存在高位为0的情况。
（2）因为函数每次只能返回一个数据，而很多题经常要求得到余数，因此把余数写成“引用”的形式传入，或者设为全局变量。

5.7 拓展欧几里得算法 （P176）

5.8 组合数

5.8.1 关于n!的一个问题

我们来思考一下n!中有多少个质因子p。例如：6！= 12345*6，于是6！有四个质因子2，两个质因子3。这个问题最朴素的解法就是计算从1~n的每个数各有多少个质因子p，然后将结果累加，时间复杂度为O(nlogn)，代码如下：

  1. int cal (int n, int p)    // 计算1~n每个数字含有多少个质因子p, 再相加
  2. {
  3.     int ans = 0;
  4.     for(int i = 2; i <= n; ++i){
  5.         int temp = i;
  6.         while (temp % p == 0){  // 只要temp还是p的倍数
  7.             ans++;
  8.             temp /= p;
  9.         }
  10.     }
  11.     return ans;
  12. }
  1. **对于这种O(nlogn)的朴素算法，当据数量很大时不可行，因此我们应寻找复杂度更小的算法。下面介绍的算法能惊人地把复杂度降到O(logn)。**<br />  ![image.png](https://cdn.nlark.com/yuque/0/2022/png/22209759/1643604599399-80e780a5-67e6-4057-a191-954e58cfc92a.png#clientId=u839aebda-2612-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=282&id=u2a4315e2&margin=%5Bobject%20Object%5D&name=image.png&originHeight=353&originWidth=797&originalType=binary&ratio=1&rotation=0&showTitle=false&size=296066&status=done&style=none&taskId=uad37eeb3-56a5-4cae-a511-7ead39d80cb&title=&width=637.6)
  1. int cal (int n, int p)    // 计算1~n每个数字含有多少个质因子p, 再相加
  2. {
  3.     int ans = 0;
  4.     while (n){
  5.         ans += n / p;
  6.         n /= p;
  7.     }
  8.     return ans;
  9. }
  1. **利用这个算法，可以很快地计算出n！的末尾有多少个零：由于末尾0的个数等于n！中因子10的个数，而这有等于n！中质因子5的个数（think about it），因此只需要代入cal(n,5)就可以得到结果。（参数p一定是质数！！ 不能直接cal(n,10)）;**<br />        ![image.png](https://cdn.nlark.com/yuque/0/2022/png/22209759/1643606124097-cc9e81bb-1280-4ab7-ac15-6c486dacc0e2.png#clientId=u839aebda-2612-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=373&id=uc95d164b&margin=%5Bobject%20Object%5D&name=image.png&originHeight=457&originWidth=781&originalType=binary&ratio=1&rotation=0&showTitle=false&size=352622&status=done&style=none&taskId=u7a9996af-2037-4075-a0e6-06b8e5425a6&title=&width=636.7999877929688)<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/22209759/1643606178919-03d42ae5-db20-4d38-8a53-0492633d7e80.png#clientId=u839aebda-2612-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=168&id=ue2efd80e&margin=%5Bobject%20Object%5D&name=image.png&originHeight=188&originWidth=718&originalType=binary&ratio=1&rotation=0&showTitle=false&size=201637&status=done&style=none&taskId=u57b4ba27-4c4e-49ab-a5b9-1f3ecc4fa93&title=&width=643.4000244140625)
  1. int cal (int n, int p)
  2. {
  3.     if(n < p)
  4.         return 0;
  5.     return n / p + cal(n / p, p);
  6. }

5.8.2 组合数的计算 （P183）