LightOJ - Trailing Zeroes (I)

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define ll long long
8. #define S 1000003
9. using namespace std;
10.  
11. bool prime[S];
12. ll primeNum[S];
13. int ind;
14.  
15. void seive(){
16.     prime[0] = prime[1] = false;
17.     int sqr = sqrt(S);
18.     for(int i = 2; i <= sqr; i++){
19.         if(prime[i]){
20.             for(int j = i+i; j <= S; j+=i)prime[j] = false;
21.         }
22.     }
23.     ind = 0;
24.     for(int i = 0; i <= S; i++)if(prime[i])primeNum[ind++] = i;
25. }
26.  
27. ll numDivisor(ll raw){
28.     ll  tot = 0, prev = 0LL, cn = 0LL;
29.     for(int i = 0; i < ind && primeNum[i]*primeNum[i] <= raw; i++){
30.         bool flag = true;
31.         while(raw%primeNum[i] == 0LL){
32.             cn++;
33.             raw /= primeNum[i];
34.         }
35.         tot = (prev*cn) + (prev+cn);
36.         prev = tot;
37.         if(raw != 1)cn = 0LL;
38.     }
39.     if(!cn)tot += tot + 1;
40.     return tot;
41. }
42.  
43. int main(){
44.     int  t, cs = 0;
45.     memset(prime, true, sizeof(prime));
46.     seive();
47.     ll n;
48.     scanf("%d", &t);
49.     while(t--){
50.         scanf("%lld", &n);
51.         if(n == 1LL){
52.             printf("Case %d: 0\n", ++cs);
53.             continue;
54.         }
55.         ll ans = numDivisor(n);
56.         printf("Case %d: %lld\n", ++cs, ans);
57.     }
58.     return 0;
59. }