# SGU 154 - Factorial

## Description

You task is to find minimal natural number $N$, so that $N!$ contains exactly $Q$ zeroes on the trail in decimal notation. As you know $N! = 1\cdot2\cdots N$. For example, $5! = 120$, 120 contains one zero on the trail.

## Input

One number $Q$ written in the input ($0\leq Q\leq 10^8$).

## Output

Write “No solution”, if there is no such number $N$, and $N$ otherwise.

## Sample Input

 1  2 

## Sample Output

 1  10 

## Solution

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27  #include using namespace std; const int MAX = 2147483647; int main() { int N; while(cin >> N) { if(N == 0) { cout << 1 << endl; continue; } int l = 1, r = MAX, ans = -1; while(l <= r) { int nMid = (l + r) >> 1; int nTmp = nMid, nCnt = 0; while(nTmp) { nCnt += nTmp / 5; nTmp /= 5; } if(nCnt == N) { ans = nMid; r = nMid - 1; } else if(nCnt < N) { l = nMid + 1; } else { r = nMid - 1; } } if(ans == -1) { cout << "No solution" << endl; } else { cout << ans << endl; } } return 0; }