C++中约数定理的实例详解

概述C++中约数定理的实例详解对于一个大于1正整数n可以分解质因数：n=p1^a1*p2^a2*......pk^ak，则n的正约数的个数就是 ：(a1+1)*(a2+1)*......*(ak+1)

C++中约数定理的实例详解

对于一个大于1正整数n可以分解质因数：n = p1^a1*p2^a2*......pk^ak，则n的正约数的个数就是  ：(a1+1)*(a2+1)*......*(ak+1)

其中a1、a2、a3…ak是p1、p2、p3，…pk的指数。

用这个定理求一个数的约数个数是非常快的，贴出一道训练题目：

hdu 1492 -求约数的个数

贴出代码：

//约数定理的 #include <iostream> #include <algorithm> #include <iterator> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <vector> #include <queue> #include <set> using namespace std;  #define ll long long  int main() {   // freopen("s.cpp","r",stdin);    ll n;   while(scanf("%lld",&n) != EOF)   {     if(!n) break;      ll sum = 1;     /* x = p1^a1*p2^a2*p3^a3...pk^ak     yueshu = (a1+1)*(a2+1)*...*(ak+1)*/     for(ll i = 2; i*i <= n; i++){       int cou = 0;       if(n%i==0){         cou = 1;         n /= i;         while(n%i==0){           cou++;           n /= i;         }       }       if(cou != 0){         sum = sum*(cou+1);       }     }     if(n != 1){       sum = sum*2;     }     if(sum==1 && n==1){       sum = 1;     }     printf("%lld\n",sum);   }   return 0; } 

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

总结

以上是内存溢出为你收集整理的C++中约数定理的实例详解全部内容，希望文章能够帮你解决C++中约数定理的实例详解所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。