Pagini recente » Cod sursa (job #910886) | Cod sursa (job #2819367) | Cod sursa (job #700667) | Cod sursa (job #609231) | Cod sursa (job #1595523)
#include <cstdio>
#include <iostream>
#include <set>
#include <climits>
#include <map>
#include <algorithm>
#include <list>
#include <vector>
#include <utility>
#include <cstdlib>
#include <iomanip>
#include <cstring>
#include <string>
using namespace std;
// BINARY SEARCH
//
// PARAMETERS:
// left, right: MEANING THE NATURAL INTERVAL [left, right]
// target: THE VALUE WE'RE SEARCHING FOR
// Function: THE FUCTION WE USE
// equality: IF WE NEED TO FIND THE EXACT VALUE
//
// RETURN:
// MINIMUM / MAXIMUM x FOR WHICH f(x) >= OR <= target
// NOTE THAT IF equality IS TRUE THE CONDITION BECOME f(x) = target
//
// USE Predicate FOR LOWER / GREATER
//
// USE Function TO WRITE THE FUNCTION YOUR PROBLEM NEEDS
//
int binaryFunction(int number) {
int ans = 0;
while (number > 0) {
number /= 5;
ans += number;
}
return ans;
}
bool binaryPredicate(int value, int target) {
return (binaryFunction(value) >= target);
}
int binarySearch(int left, int right, int target, bool equality) {
while (left < right) {
int mid = (left + right) / 2;
if (binaryPredicate(mid, target))
right = mid;
else
left = mid + 1;
}
if (equality && binaryFunction(left) != target)
return -1;
return left;
}
// SIEVE FOR PRIME NUMBERS
//
// PARAMETERS:
// primality: A BOOLEAN VECTOR WHERE primality[i] = TRUE IF i IS A PRIME
// maxValue: THE MAX VALUE SIEVE WILL GO TO. NOTE THAT i < maxValue
//
// RETURN:
// COMPLETED VECTOR primality WITH THE FUNCTIONALITY DESCRIPTED ABOVE
//
// IF TAKES TOO LONG, USE IT IN MAIN
//
void sieve(bool primality[], int maxValue) {
for (int i = 2; i < maxValue; i++) {
primality[i] = true;
}
for (int i = 2; i * i < maxValue; i++) {
if (primality[i]) {
for (int j = i * i; j < maxValue; j += i) {
primality[j] = false;
}
}
}
}
// GCD AND LCM
//
// PARAMETERS:
// a, b: THE NUMBERS WE WANT TO FIND THEIR GCD / LCM
//
// RESULT:
// THE GCD / LCM OF THE NUMBERS
//
// IF WRONG ANSWER, CHANGE TO LONG / LONG LONG
//
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
// MODULAR EXPONENTIATION
//
// PARAMETERS:
// base: THE BASE FOR EXPONENTIATION
// exp: THE EXPONENT FOR EXPONENTIATION
// mod; THE MODOLUS
//
// RETURN:
// THE RESULT OF (base ^ mod) % mod
//
// IF WRONG ANSWER, CHANGE TO LONG / LONG LONG
//
int modExp(int base, int exp, int mod) {
if (mod == 1)
return 0;
int ans = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1)
ans = (ans * base) % mod;
exp >>= 1;
base = (base * base) % mod;
}
return ans;
}
int main() {
// freopen("tt.txt", "r", stdin);
freopen("fact.in", "r", stdin);
freopen("fact.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
int p;
cin >> p;
int ans = binarySearch(1, 5 * p, p, true);
cout << ans;
return 0;
}