Cod sursa(job #2757263)

Utilizator contusContus Amogus contus Data 4 iunie 2021 19:35:23
Problema Factorial Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#define int long long
using namespace std;

ifstream cin("fact.in");
ofstream cout("fact.out");

// x! = 2^a * 5^b * T
// a<b

static int cabasFunctii(int x) { // luam x ----> cati de 0 are x! la final
  int cntb=0;
  //while(x>0) {
    //cnta+=x/2;
    //x/=2;
  //}
  while(x>0) {
    cntb+=x/5;
    x/=5;
  }
  return cntb;
}

signed main() {
  int k;
  cin >> k;
  //while (i<1000000000000000LL) {
    //if(cabasFunctii(i)==k) {
      //cout << i;
      //i=1000000000000000LL;
    //}
    //i++;
  //}
  int l=0,r=1000000000000000LL,mid;
  
  // l este cea mai mare valoare astfel incat cabasFunctii(l)<k
  // r este cea mai mica valoare astfel incat cabasFunctii(r)>=k
  // l si r sunt totodata marginile segmentului relevant
  while(r-l>1) {
    mid=(l+r)/2;
    if(cabasFunctii(mid)<k)
      l=mid;
    else // cabasFunctii(mid)>=k
      r=mid;
  } 
  
  if(cabasFunctii(r)==k)
    cout << r <<'\n';
  else
    cout << "-1\n";
}
/**
 * 
 * k --> expLeg(n) = k (n minim = ?)
 * 
 * | 
 * |
 * |            36
 * |                  
 * |                  ___  
 * |             _____   
 * |             
 * |    18  ____
 * |    ____     
 * | ___         
 * +-----------------------
 *     lr
 * 
 * 1095
 */