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 阅读(1186) 评论(1)  编辑 收藏 引用

评论

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

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


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