好资源导航 » 文章资讯 » C++中约数定理的实例详解

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

2024-02-16 17:08:05 383

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的指数。

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

hdu1492-求约数的个数

贴出代码：

//约数定理的
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
usingnamespacestd;

#definelllonglong

intmain()
{
//freopen("s.cpp","r",stdin);

lln;
while(scanf("%lld",&n)!=EOF)
{
if(!n)break;

llsum=1;
/*x=p1^a1*p2^a2*p3^a3...pk^ak
yueshu=(a1+1)*(a2+1)*...*(ak+1)*/
for(lli=2;i*i<=n;i++){
intcou=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);
}
return0;
}

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

返回顶部
3162201930
czq8825@qq.com

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

热门推荐

随机推荐