Friday 28 July 2017

Lightoj 1090 - Trailing Zeroes (II)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long unsigned
  4. ll tf, ff, tn, fn;  
  5. void ncr(ll n, ll r){
  6.     ll devf = 5, devt = 2;
  7.     ll p = n, q = r;
  8.     while(n>=devf){
  9.         ff+= n/devf;devf*=5;
  10.     }
  11.    
  12.     while(n>=devt){
  13.         tf+= n/devt;devt*=2;
  14.     }
  15.     n = p;
  16.     devf = 5, devt = 2;
  17.     while(r>=devf){
  18.         ff-= r/devf;devf*=5;
  19.     }
  20.     while(r>=devt){
  21.         tf-= r/devt;devt*=2;
  22.     }
  23.     n = p;
  24.     q = p-q;
  25.     devf = 5, devt = 2;
  26.     while(q>=devf){
  27.         ff-= q/devf;devf*=5;
  28.     }
  29.     while(q>=devt){
  30.         tf-= q/devt;devt*=2;
  31.     }
  32. }
  33. void num(ll n){
  34.     while(n%2 == 0){
  35.         n/= 2;tn++;
  36.     }
  37.     while(n%5 == 0){
  38.         n/= 5;fn++;
  39.     }
  40. }
  41.  
  42. int main(){
  43.     //cout<<zero_in_fac(1000000);
  44.     int ts;
  45.     cin>>ts;
  46.     for(int i = 1; i <= ts; i++){
  47.         tf = 0, ff = 0, tn = 0, fn = 0;
  48.         ll n, r, p, q, ans;
  49.         scanf("%llu%llu%llu%llu"&n, &r, &p, &q);
  50.         ncr(n, r);
  51.         num(p);
  52.         tn*=q;
  53.         fn*=q;
  54.         ans = min(tn+tf, fn+ff);
  55.         printf("Case %d: %llu\n", i, ans);
  56.     }
  57.     return 0;
  58. }

No comments:

Post a Comment

Most Featured Post

Lightoj 1159 - Batman

http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...