The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 2603-Brave balloonists 求BigInt的最大公约数(用数论知识解决)

原来这道题用数论的方法如此简单啊,这样就不用进行大数操作了 呵呵;
数论算法如下:


若正整数n可分解为(p1^a1)*(p2^a2)*…*(pk^ak)
其中pi为两两不同的素数,ai为对应指数
n的约数个数为(1+a1)*(1+a2)*….*(1+ak)

做完不禁赞叹到,此法甚妙~定要掌握之 呵呵

#include<iostream>
#include
<cmath>
#include
<algorithm>
using namespace std;


int a[10001];

int main ()
{

    
int n;
    
int i;
    
int j;
    
for(i=1;i<=10;i++)
    
{

        scanf(
"%d",&n);
        
for(j=2;;j++)
        
{

            
while(n%j==0&&n!=1)
            
{
                a[j]
++;
                n
/=j;
            }

            
if(n==1)
                
break;
        }




    }

    
int result=1;
    
for(i=2;i<=10000;i++)
    
{

        
if(a[i]!=0)
        
{

            result
=result*(a[i]+1);
        }

    }

    printf(
"%d\n",result%10);
    system(
"pause");
    
return 0;

}


 


posted on 2009-03-07 00:36 abilitytao 阅读(1145) 评论(1)  编辑 收藏 引用

评论

# re: POJ 2603-Brave balloonists 求BigInt的最大公约数(用数论知识解决) 2009-03-07 09:57 cppexplore

博主将文章 发往首页精华的 时候 稍微斟酌下 尤其是很多篇一起放上来的时候,没多少时间一篇一篇的审核,多谢。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理