ACMSGURU 154 - Factorial

Reck Zhang

发布于 2021-08-11 11:13:47

2510

发布于 2021-08-11 11:13:47

Factorial

Problem 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! = 12…*N. For example, 5! = 120, 120 contains one zero on the trail.

Input

One number Q written in the input (0<=Q<=10^8).

Output

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

Sample test(s)

Input

Output

Solution

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);

    int q;
    std::cin >> q;

    if(q == 0) {
        std::cout << 1 << std::endl;
    }

    long long left = 5;
    long long right = 5 * q;
    long long res = -1;
    while(left <= right) {
        long long mid = (left + right) / 2;
        long long tmpMid = mid;
        int count = 0;
        while(tmpMid != 0) {
            tmpMid /= 5;
            count += tmpMid;
        }
        if(count == q) {
            res = mid;
            right = mid - 1;
        } else if(count > q) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    if(res == -1) {
        std::cout << "No solution" << std::endl;
    } else {
        std::cout << res << std::endl;
    }

    return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除

contains