POJ Brave balloonists 解题报告

时间：2010-06-22 来源：华南理工大学

一、问题描述

http://acm.pku.edu.cn/JudgeOnline/problem?id=2603

二、解题思路

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

三、代码

#include<iostream>
using namespace std;
const int MAXN=10007;
int prim[MAXN],cnt;
bool b[MAXN];
int m[MAXN];
//获取质数表
void GetPrim()
{
    int i,j;
    cnt=0;
    for(i=2;i<MAXN;++i)
    {
        if(b[i]==0)
        {
            prim[cnt++]=i;
            for(j=i+i;j<MAXN;j+=i)
                b[j]=1;
        }
    }
}
int main()
{
    int i;
    int a;
    int j;
    int sum;
    memset(b,0,sizeof(b));
    memset(m,0,sizeof(m));
    GetPrim();
    for(i=0;i<10;++i)
    {
        scanf("%d",&a);
        j=0;
        while(a>1)
        {
            while(a>1 && a % prim[j] ==0)
            {
                sum++;
                m[ prim[j] ]++;
                a/=prim[j];
            }
            j++;
        }
    }
    int res=1;
    for(i=0;i<MAXN;++i)
    {
        if(m[i]>0)
        {
            res*=(m[i]+1);
            res%=10;
        }
    }
    printf("%d\n",res%10);
    return 0;
}