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

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

数论_URAL1049_算数基本定理  

2011-08-09 09:50:05|  分类: ACM_数论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
#include <cstdio>
#include <algorithm>

using namespace std;

const int n = 10;
int a[11];
int r[10010];

/*
算数基本定理可以这样理解:一切大数都可以拆分,大数运算的时候可以拆分之后再运算
首先根据算数基本定理吧ai 分解为
ai = p1^r1 * p2^r2 * ... * pk^rk
然后相乘,得
a = a1 * a2 * ... * a10
a的分解为ai的分解相乘,
a = p1^s1 * p2^s2 *... * pk^sk
因子的个数就是
s = (s1+1)*(s2+1)*...*(sk+1)
最终的答案就是s % 10
在计算的 时候为了避免超longlong范围
s *= (si+1)
s %= 10

*/
void dcomp()
{
        int i;
        int j;
        int k;
        for(i = 1;i <= n;i ++)
        {
                for(j = 2;j <= a[i];j ++)
                {
                        while(a[i] % j == 0)//这里刚开始写的是if贡献了几次WA!
                        {
                                r[j] ++;
                                a[i] /= j;
                        }
        
                }        
                if(a[i] != 1)
                        r[a[i]] = 1;
        }        

}

void work()
{
        int i;
        for(i = 0;i <= 10000;i ++)
                r[i] = 0;
        dcomp();
        long long ans = 1;
        for(i = 1;i <= 10000;i ++)
        {
                if(r[i] != 0)
                {
                        ans *= ((r[i]+1) % 10);
                        ans %= 10;
                }        
        }
        printf("%lld\n",ans);

}


int main()
{
        int i;
        for(i = 1;i <= n;i ++)
                scanf("%d",&a[i]);
        work();



        return 0;
}
  评论这张
 
阅读(127)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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