找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 626|回复: 1
收起左侧

[资源分享] 32 Factorial Number

[复制链接]

48

主题

5

精华

383

积分

高级会员

Rank: 3Rank: 3

积分
383

最佳新人

发表于 6-2-2015 11:58 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
先找到要求值的上界,然后用二分法

  1.     public static long findM(long n) {
  2.         int i = 0;
  3.         // First, find upper bound
  4.         while(trailingZeros((long) Math.pow(2, i)) < n) {
  5.             i++;
  6.         }
  7.         long left = 0, right = (long) Math.pow(2, i);
  8.         // binary search find smallest valid one
  9.         while(left <= right) {
  10.             long mid = left + (right-left)/2;
  11.             long zeros = trailingZeros(mid);
  12.             if(zeros >= n) {
  13.                 right = mid - 1;
  14.             } else {
  15.                 left = mid + 1;
  16.             }
  17.         }
  18.         return left;
  19.     }

  20.     private static long trailingZeros(long n) {
  21.         long cnt = 0, base = 5;
  22.         while(n/base != 0) {
  23.             cnt += n / base;
  24.             base *= 5;
  25.         }
  26.         return cnt;
  27.     }
复制代码


2

主题

0

精华

100

积分

资深会员

Rank: 2

积分
100
发表于 2-27-2016 01:36 AM | 显示全部楼层
多谢
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表