首页 > 代码库 > Light OJ 1028 - Trailing Zeroes (I) (数学-因子个数)

Light OJ 1028 - Trailing Zeroes (I) (数学-因子个数)

题目链接:http://www.lightoj.com/volume_showproblem.php?problem=1028

题目大意:n除了1有多少个因子(包括他本身)

解题思路:对于n的每个因子, 可以用n的所有素因子排列组合而来, n = (a1x1) * (a2 x2) * (a3x3)...*(anxn), 其中ai为n的素因子,那么n的因子的个数等同于(x1 + 1) * (x2 + 1) * (x3 + 1) ... * (xn + 1)中排列, 因为其中一种排列肯定为所有素因子的幂指数为0, 那么这个因子就是1, 这个最后去掉就好。 最后只求n的每个素因子的幂指数,即可求解

代码如下:

技术分享
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-10;

long long prime[100003], p = 0;
bool is_prime[1000003];

void init()
{
    memset(is_prime, true, sizeof(is_prime));
    for(int i=2; i<=1000000; ++ i)
    {
        if(is_prime[i])
        {
            prime[p++] = i;
            for(int j=i; j<=1000000; j+=i)
                is_prime[j] = false;
        }
    }
}

void solve(int cases)
{
    long long n;
    scanf("%lld", &n);
    long long ans = 1;
    for(int i=0; i<p&&prime[i]*prime[i]<=n; ++ i)
    {
        int res = 0;
        while(n % prime[i] == 0)
        {
            n /= prime[i];
            res ++;
        }
        ans *= (res + 1);
    }
    if(n > 1)
        ans *= 2;
    printf("Case %d: %lld\n", cases, ans-1);
}

int main()
{
    int n;
    scanf("%d", &n);
    init();
    for(int i=1; i<=n; ++i)
    {
        solve(i);
    }
    return 0;
}
View Code

 

Light OJ 1028 - Trailing Zeroes (I) (数学-因子个数)