LightOJ - 1138 - Trailing Zeroes (III)

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 n;
13.  
14. int BS(int h, int l){
15.     int p, q, m, f = 0;
16.     while(h >= l){
17.         p = h+l;
18.         if(p&1)p += 5;
19.         m = p/2;
20.         q = m;
21.         if(f == m)return -1;
22.         f = m;
23.         int ans = 0;
24.         while(q > 0){
25.             ans += q/5;
26.             q /= 5;
27.         }
28.         if(ans == n)return m;
29.         else if(ans > n)h = m;
30.         else l = m;
31.     }
32.     return -1;
33. }
34.  
35. int main(){
36.     int t, cs = 0;
37.     scanf("%d", &t);
38.     while(t--){
39.         scanf("%d", &n);
40.         int high = 5*n;
41.         int low = 5;
42.         int a = BS(high, low);
43.         printf("Case %d: ", ++cs);
44.         printf((a < 0)?"impossible\n":"%d\n", a);
45.     }
46.     return 0;
47. }

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. }

LightOJ - 1077 - How Many Points?

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 main(){
13.     int t, cs = 0;
14.     LL x1, x2, y1, y2;
15.     LL a, b;
16.     scanf("%d", &t);
17.     while(t--){
18.         scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
19.         LL p, q;
20.         if(x1 < 0 && x2 < 0)p = abs(abs(x1)-abs(x2));
21.         else if(x1 >= 0 && x2 >= 0)p = abs(x1-x2);
22.         else if(x1 < 0 && x2 >= 0)p = abs(x1)+x2;
23.         else p = x1+abs(x2);
24.  
25.         if(y1 < 0 && y2 < 0)q = abs(abs(y1)-abs(y2));
26.         else if(y1 >= 0 && y2 >= 0)q = abs(y1-y2);
27.         else if(y1 < 0 && y2 >= 0)q = abs(y1)+y2;
28.         else q = y1+abs(y2);
29.  
30.         LL ans = __gcd(p, q)+1;
31.         printf("Case %d: %lld\n", ++cs, ans);
32.     }
33.     return 0;
34. }

LightOJ - 1067 - Combinations

1. /****************#####    بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم   #####******************
2. __________________________________________________________________________
3. ######################  Ya-Seen Arafat(ACWizard) #########################
4. ######################        UAP-CSE-33B        #########################
5. *************************************************************************/
6. #include <bits/stdc++.h>
7. #define M (long long)1000003
8. #define S 1000003
9. #define LL long long
10. using namespace std;
11.  
12. LL factorial[M+3];
13.  
14. void findFact(){
15.     factorial[0] = 1;
16.     for(int i = 1; i < S; i++){
17.         factorial[i] = factorial[i-1] * i;
18.         factorial[i] %= M;
19.     }
20. }
21.  
22. LL modInverse(LL a, LL p){
23.     if(p == 0)return 1LL;
24.     else if(p%2)return ((a%M)*(modInverse(a, p-1)%M))%M;
25.     else{
26.         LL x = modInverse(a, p/2);
27.         return (x%M*x%M)%M;
28.     }
29. }
30.  
31. int main(){
32.     memset(factorial, 1LL, sizeof(factorial));
33.     findFact();
34.     int t, cs = 0;
35.     LL n, k;
36.     scanf("%d", &t);
37.     while(t--){
38.         scanf("%d %d", &n, &k);
39.         LL y = factorial[n];
40.         LL z = (factorial[n-k]%M*factorial[k]%M)%M;
41.         LL ans = modInverse(z, M-2LL);
42.         ans = (y%M*ans%M)%M;
43.         printf("Case %d: %lld\n", ++cs, ans);
44.     }
45.     return 0;
46. }

LightOJ - 1045 - Digits of Factorial

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. double cuS[S];
12.  
13. void cumulativeSum(){
14.     cuS[1] = log((double)1);
15.     for(int i = 2; i < S; i++){
16.         cuS[i] = cuS[i-1] + log((double)i);
17.     }
18. }
19.  
20. int main(){
21.     int  t, cs = 0, n, base;
22.     cumulativeSum();
23.     scanf("%d", &t);
24.     while(t--){
25.         scanf("%d %d", &n, &base);
26.         double value = cuS[n];
27.         value /= log((double)base);
28.         ll ans = value;
29.         ans += 1;
30.         printf("Case %d: %lld\n", ++cs, ans);
31.     }
32.     return 0;
33. }

LightOJ - 1035 - Intelligent Factorial Factorization

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 103
9. using namespace std;
10.  
11. int prime[S];
12. int primeNum[S];
13. int ans[S];
14. int ind;
15.  
16. void seive(){
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] = 0;
21.         }
22.     }
23.     ind = 0;
24.     for(int i = 2; i < S; i++)if(prime[i])primeNum[ind++] = i;
25. }
26.  
27. void numDivisor(int number){
28.     int cn = 0;
29.     for(int i = 0; i < ind; i++){
30.         for(int k = 2; k <= number; k++){
31.             while(prime[k]%primeNum[i] == 0){
32.                 cn++;
33.                 prime[k] /= primeNum[i];
34.             }
35.             ans[primeNum[i]] += cn;
36.             cn = 0;
37.         }
38.     }
39. }
40.  
41. int main(){
42.     int  t, cs = 0, n;
43.     memset(prime, 1, sizeof(prime));
44.     seive();
45.     scanf("%d", &t);
46.     while(t--){
47.         scanf("%d", &n);
48.         memset(ans, 0, sizeof(ans));
49.         for(int i = 2; i < S; i++)prime[i] = i;
50.         numDivisor(n);
51.         printf("Case %d:", ++cs);
52.         bool flag = true;
53.         for(int i = 2; i <= 100; i++){
54.             if(ans[i] && flag)printf(" %d = %d (%d)", n, i, ans[i]), flag = false;
55.             else if(!flag && ans[i])printf(" * %d (%d)", i, ans[i]);
56.         }
57.         puts("");
58.     }
59.     return 0;
60. }