LightOJ - 1090 - Trailing Zeroes (II)

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define M 1000003
8. #define S 1000003
9. #define LL long long
10. using namespace std;
11.  
12. int find_p(int a, int b){
13.     int cn = 0;
14.     while(a > 0){
15.         cn += (a/b);
16.         a /= b;
17.     }
18.     return cn;
19. }
20.  
21. int find_pr(int a, int b){
22.     int cn = 0;
23.     while(!(a%b)){
24.         cn++;
25.         a /= b;
26.     }
27.     return cn;
28. }
29.  
30. int main(){
31.     int t, n, r, p, q, c, cs = 0;
32.     scanf("%d", &t);
33.     while(t--){
34.         scanf("%d %d %d %d", &n, &r, &p, &q);
35.         c = n-r;
36.         int five_up = 0, five_down = 0, two_up = 0, two_down = 0;
37.  
38.         five_up = find_p(n, 5);
39.         two_up = find_p(n, 2);
40.         five_down = find_p(c, 5);
41.         five_down += find_p(r, 5);
42.         two_down = find_p(c, 2);
43.         two_down += find_p(r, 2);
44.  
45.         five_up += (q*find_pr(p, 5));
46.         two_up += (q*find_pr(p, 2));
47.  
48.         int five, two;
49.         five = five_up-five_down;
50.         two = two_up-two_down;
51.         int ans = min(five, two);
52.         printf("Case %d: %d\n", ++cs, ans);
53.     }
54.     return 0;
55. }