- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long unsigned
- ll tf, ff, tn, fn;
- void ncr(ll n, ll r){
- ll devf = 5, devt = 2;
- ll p = n, q = r;
- while(n>=devf){
- ff+= n/devf;devf*=5;
- }
- while(n>=devt){
- tf+= n/devt;devt*=2;
- }
- n = p;
- devf = 5, devt = 2;
- while(r>=devf){
- ff-= r/devf;devf*=5;
- }
- while(r>=devt){
- tf-= r/devt;devt*=2;
- }
- n = p;
- q = p-q;
- devf = 5, devt = 2;
- while(q>=devf){
- ff-= q/devf;devf*=5;
- }
- while(q>=devt){
- tf-= q/devt;devt*=2;
- }
- }
- void num(ll n){
- while(n%2 == 0){
- n/= 2;tn++;
- }
- while(n%5 == 0){
- n/= 5;fn++;
- }
- }
- int main(){
- //cout<<zero_in_fac(1000000);
- int ts;
- cin>>ts;
- for(int i = 1; i <= ts; i++){
- tf = 0, ff = 0, tn = 0, fn = 0;
- ll n, r, p, q, ans;
- scanf("%llu%llu%llu%llu", &n, &r, &p, &q);
- ncr(n, r);
- num(p);
- tn*=q;
- fn*=q;
- ans = min(tn+tf, fn+ff);
- printf("Case %d: %llu\n", i, ans);
- }
- return 0;
- }
Friday 28 July 2017
Lightoj 1090 - Trailing Zeroes (II)
Subscribe to:
Post Comments (Atom)
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...
-
Problem link: Problem Analysis: It is actually a basic Bisection problem , as we can see here we can not actually find a formula fo...
-
http://lightoj.com/volume_showproblem.php?problem=1382 Problem analysis: This is a rare problem i wrote about so far. After much strugg...
No comments:
Post a Comment