SGU154――Factorial （poj1401变形题――数论+二分） - c++编程基础

154. Factorial

time limit per test: 0.5 sec.
memory limit per test: 4096 KB input: standard input
output: standard output

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 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

2 Output

10 题目描述：输入一个数n、求某个数的阶乘后面有n个0的数p； 会了poj1401就好办了、直接来个二分搜素。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
             #include
             
               #include
              
                #define N 0x7fffffff using namespace std; int num0(int n) { int count=0; while(n) { count+=n/5; n/=5; } return count; } void find(int w) { int left=0,right=N,mid; while(left<=right) { mid=(left+right)>>1;//位运算速度快 // mid=(left+right)/2; if(num0(mid)>=w) right=mid-1; else left=mid+1; } if(num0(left)==w) printf("%d\n",left); else puts("No solution"); } int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==0) printf("1\n"); else { find(n); } } return 0; }

[submit] [forum]