154. Factorial
time limit per test: 0.25 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!中隻要把每個數都拆分為質因數的積,則隻需要
//質因數5的個數即可,因為2的個數會比5多很多,是以質因數有多少5,
//尾部就有多少0........
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int num(int n)
{
int cnt=0;
while(n)
{
cnt+=n/5;//
n/=5;
}
return cnt;
}
void find(int n)
{
int left=0,right=INF,mid;
while(left<=right)
{
mid=(left+right)/2;
if(num(mid)>=n)
right=mid-1;
else
left=mid+1;
}
if(num(left)==n)
printf("%d\n",left);
else
printf("No solution\n");
}
int main(){
int n;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
printf("1\n");
else
find(n);
}
return 0;
}
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int fun(int x)
{
int sum=0;
while(x)
{
sum+=x/5;
x/=5;
}
return sum;
}
int main(){
int m;
while(scanf("%d",&m)!=EOF)
{
if(m==0)
{
printf("1\n");
continue;
}
int n=m*4/5*5;
while(fun(n)<m)
{
n+=5;
}
if(fun(n)==0)
printf("%d\n",n);
else
printf("No solution\n");
}
return 0;
}