【二分+数学公式】Trailing Zeroes (III)

传送门:这里

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

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains an integer Q (1 ≤ Q ≤ 108) in a line.

Output

For each case, print the case number and N. If no solution is found then print ‘impossible’.

Sample Input

Output for Sample Input

3

1

2

5

Case 1: 5

Case 2: 10

Case 3: impossible

核心在于:如何快速求阶乘后有多少个0,这个公式我之前就写过啦,传送一下。(只有5能产生0,即求因子5的个数)

相同的公式,再加上二分,完成:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL sum(LL N)
{
  LL ans = 0;
  while (N)
  {
    ans += N / 5;
    N /= 5;
  }
  return ans;
}

int main()
{
  int t = 0;
  cin >> t;
  int cas = 0;
  while (t--)
  {
    int q;
    scanf("%d", &q);
    LL left = 1, ri = 100000000000;
    LL ans = 0;
    while (ri >= left)
    {
      int mid = (left + ri) >> 1;
      if (sum(mid) == q)
      {
        ans = mid;
        ri = mid - 1;
      }
      else if (sum(mid) > q)
        ri = mid - 1;
      else
        left = mid + 1;
    }
    printf("Case %d: ", ++cas);
    if (ans)
      printf("%lld\n", ans);
    else
      printf("impossible\n");
  }
  return 0;

}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

3 × 3 =