注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

数论_算数基本定理  

2011-08-01 20:12:16|  分类: ACM_数论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
众所周知:

算数基本定理:每一个大于1的整数n,都可以唯一分解成有限个指数的乘积:
n = p1^r1 * p2^r2 * .... * pk^rk
其中,p1 < p2 < ... < pk 均为质数,r1,r2,..,rk均为正整数。
根据算数基本定理可以求解
n的所有因子之和 (1 + .. + p1^r1)*(1 + .. + p2^r2)*(1 + .. + pk^rk)

需先求出pi,和ri
A为要分解的数
int p[MAXN] 是质数p数组
int r[MAXN] 是幂r数组

void dcomp()
{
        cont = 0;
        long long i;
        for(i = 2;i*i <=A; i++)
        {
                if(A % i == 0)
                p[++cont] = i;
                while(A % i == 0)
                {
                        r[cont] ++;
                        A /= i;
                }
        } 
        if(A != 1)
        {
                  p[++cont] = A;
                  r[cont] = 1; 
         } 
}

然后利用二分法求出等比数列 的和即可

  评论这张
 
阅读(245)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018