Pagini recente » Cod sursa (job #999184) | Cod sursa (job #121917) | Borderou de evaluare (job #1178961) | Cod sursa (job #1168115) | Cod sursa (job #3332669)
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
unordered_map<ull, ull> um;
ull ApplyLegendre(ull factorial, ull prime) {
ull power = prime;
ull result = 0;
while (power <= factorial) {
result += (factorial / power);
power *= prime;
}
return result;
}
bool EnoughFactors(ull mid) {
for (auto [prime, power] : um) {
if (ApplyLegendre(mid, prime) < power) {
return false;
}
}
return true;
}
ull BinarySearch(ull number_of_zeros_at_end) {
if (number_of_zeros_at_end == 0) return 1ULL;
um[2] = number_of_zeros_at_end;
um[5] = number_of_zeros_at_end;
ull left, right;
ull ans = 0;
left = 1;
right = 5ULL * number_of_zeros_at_end;
while (left <= right) {
ull mid = left + (right - left) / 2;
if (EnoughFactors(mid)) {
ans = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
if (ApplyLegendre(ans, 5) == number_of_zeros_at_end)
return ans;
else
return -1;
}
int main() {
freopen("fact.in", "r", stdin);
freopen("fact.out", "w", stdout);
ull P;
scanf("%llu",&P);
ull result = BinarySearch(P);
printf("%llu\n",result);
return 0;
}