URAL 1049 Brave Balloonists

URAL_1049

    把各个数分解素因子之后应用乘法原理计算约数的个数即可。

#include<stdio.h>
#include<string.h>
#define MAXD 10010
int isprime[MAXD], prime[MAXD], P, h[MAXD];
void prepare()
{
    int i, j, k;
    P = 0;
    memset(isprime, -1, sizeof(isprime));
    for(i = 2; i <= 10000; i ++)
        if(isprime[i])
        {
            prime[P ++] = i;
            for(j = i * i; j <= 10000; j += i)
                isprime[j] = 0;
        }
}
void solve()
{
    int i, j, k, x;
    for(i = 0; i < P; i ++)
        h[i] = 1;
    for(i = 0; i < 10; i ++)
    {
        scanf("%d", &x);
        for(j = 0; j < P; j ++)
            while(x % prime[j] == 0)
                ++ h[j], x /= prime[j];
    }
    k = 1;
    for(i = 0; i < P; i ++)
        k = (k * h[i]) % 10;
    printf("%d\n", k);
}
int main()
{
    prepare();
    solve();
    return 0;
}