Cod sursa(job #2660415)

Utilizator mohamedsobhi777Mohamed Sobhy mohamedsobhi777 Data 19 octombrie 2020 11:36:19
Problema Factorial Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e5 + 7, mod = 1e9 + 7;
const ll inf = 2e18;

// How interesting!

ll x;

ll check(ll X)
{
        ll ret = 0;
        ll cnt = 0;
        while (X)
        {
                X /= 5;
                ret += X;
        }
        return ret;
}

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        freopen("fact.in", "r", stdin);
        freopen("fact.out", "w", stdout);
        //freopen("in.in", "r", stdin);
        cin >> x;
        ll lo = 1, hi = 1e9;
        ll ans;
        while (lo <= hi)
        {
                ll mid = (lo + hi) >> 1ll;
                if (check(mid) >= x)
                {
                        hi = mid - 1;
                        ans = mid;
                }
                else
                {
                        lo = mid + 1;
                }
        }
        cout << (check(ans) == x ? ans : -1);
        return 0;
}

/*
        - bounds sir (segtree = 4N, eulerTour = 2N, ...)
        - a variable defined twice?
        - will overflow?
        - is it a good complexity?
        - don't mess up indices (0-indexed vs 1-indexed)
        - reset everything between testcases. 
*/