Light OJ 1028 Trailing Zeroes (I) 求n因子数

本文主要是介绍Light OJ 1028 Trailing Zeroes (I) 求n因子数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源：Light OJ 1028

题意：求一个数转化成任意进制后末尾有0的种数 就是一个数因子的个数

思路：一个数可以被分解成若干素数相乘 p1^x1*p2^x2*...*pn^xn

根据乘法原理 因子数为 (x1+1)*(x2+1)*...*(xn+1)

注意剪枝

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
//筛素数 
const int maxn = 1000010;
bool vis[maxn];
int prime[maxn];int sieve(int n)
{memset(vis, 0, sizeof(vis));vis[0] = vis[1] = 1;int c = 0;for(int i = 2; i <= n; i++)if(!vis[i]){prime[c++] = i;for(int j = 2*i; j <= n; j += i)vis[j] = 1;}return c;
}int main()
{int c = sieve(1000000);int cas = 1;int T;scanf("%d", &T);while(T--){long long n, ans = 1;scanf("%lld", &n);for(int i = 0; i < c && prime[i]*prime[i] <= n; i++){if(prime[i] > n)break;if(n % prime[i] == 0){long long sum = 1;while(n % prime[i] == 0){sum++;n /= prime[i];}ans *= sum;}}if(n > 1)ans *= 2;printf("Case %d: %lld\n", cas++, ans-1);}return 0;
}

 

 

这篇关于Light OJ 1028 Trailing Zeroes (I) 求n因子数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---