算法中的数学：约数

1.求一个整数的全部约数

   对于一个整数x，他的此中一个约数若为i，那么x/i也是x的一个约数。而此中一个约数的大小肯定小于等于根号x（完全平方数则两个约数都为根号x），所以我们只需要遍历到根号x，然后盘算出另一个约数即可
  代码实现：
 

1. int a[N];
2. int cnt;
3. void getnum(int x)
4. {
5.    for(int i = 1; i <= x/i; i++)
6.    {
7.         if(x%i == 0)
8.          {
9.              a[++cnt] = i;
10.              if(x/i != i)
11.                {
12.                   a[++cnt] = x/i;
13.                }
14.           }
15.     }
16. }
17.             

复制代码

时间复杂度为O(根号n)
  2.求（1~n）的每个数的约数集合

   假如我们对每个数都使用试除法会导致算法时间复杂度过高，为O（n*根号n）
  所以我们使用正难则反的头脑，遍历1~n的全部数，然后将它作为约数给到全部他的倍数。
  图示：
  

  这里我们演示了怎样使用该方法将每个数的约数求出来。
  这样子时间复杂度就来到了nlogn
  代码实现：
 

1. int n;
2. vector<int> a[N];
3. void func()
4. {
5. for(int i = 1; i <= n; i++)
6.   {
7.    for(int j = 1; i*j <= n; j++)
8.      {
9.        a[i*j].push_back(i);
10.      }
11.   }
12. }      

复制代码

3.约数个数定理

   根据唯一分解定理我们可知：一个数可以被拆分成多个质数的任意次方相乘
  而这些不同的质数颠末组合就可以得到num的约数
  图示：

  而总结出来的公式就是：
  (次方加1）*(次方加1) *.......
  增补：
试除法求单个数的约数个数
  方法一：遍历1~根号n的数将cnt返回
  方法二：分解质因数后套用公式盘算
  4.约数和定理

   盘算方法：将每个质因数的全部分别种类相加，记为sum，然后不同的质因数的sum乘起来
  

  右边我们就是在盘算约数之和的具体过程
   5.例题解说

   

  审题：
本题需要我们求出一到n的数的全部约数的个数之和
  思路：
方法一：暴力解法
  我们可以用试除法盘算1到n每个数的全部约数，然后将cnt累加起来，外层循环为遍历1~n，内层为试除法，时间复杂度为O（n根号n）
  运行次数为1e12，肯定超时
  方法二：正难则反
  我们可以遍历1~n，不过这里的i含义是约数，用n/i可以求出当前约数一共出现的次数，然后就累加起来。但是这样就要运行n次，也就是1e8次，照旧有大概超时
  优化：由于当i小于等于n/2的时候，约数出现次数大于等于1，而i大于n/2的时候，约数次数肯定为1，所以我们只用遍历到n/2即可，背面的次数都为1，所以背面的约数的出现次数等于背面的约数个数（n-n/2）
  
  解题：
 

1. #include<iostream>
2. using namespace std;
3. typedef long long ll;
4. ll n;
5. ll cnt;
6. int main()
7. {
8.    cin >> n;
9.     for(int i = 1; i <= n/2; i++)
10.     {
11.          cnt += n/i;
12.     }
13.     cnt += n-n/2;
14.     cout << cnt << endl;
15.     return 0;
16. }

复制代码

  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。