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

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

UVA 10139  

2010-03-18 15:57:00|  分类: uva |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
给定a,b问b是否能整除a!
需要用到一个定理,n!中素数p的指数为sigma(i=p;i<=n;i*=p)n/i
先将b分解因式,记录下指数,然后用上面的定理来比较指数即可
#include<cstdio>
#include<cstring>
long a[100],b[100],a1,a2;
int k;
long aa(long n,long p){
    long sum=0;
    for(long pp=p;pp<=n;pp*=p)
      sum+=n/pp;
    return sum;
}
void bb(long n){
     k=0;
     memset(b,0,sizeof(b));
     for(long i=2;i*i<=n;i++)
       if(!(n%i)){
         a[k]=i;
         while(!(n%i)){
           b[k]++;
           n/=i;
         }
         k++;
       }
     if(n>1){a[k]=n;b[k++]=1;}
}
int main(){
    while(scanf("%ld%ld",&a1,&a2)!=EOF)
      if(a1>a2)
        printf("%ld divides %ld!\n",a2,a1);
      else{
        bb(a2);
        int mark=1;
        for(int i=0;i<k;i++)
          if(aa(a1,a[i])<b[i]){           
            mark=0;
            break;
          }
        if(mark)printf("%ld divides %ld!\n",a2,a1);
        else printf("%ld does not divide %ld!\n",a2,a1);
      }
    return 0;
}

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

历史上的今天

评论

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

页脚

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