You are not logged in. Please login at www.codechef.com to post your questions!

×

INLO25 - Editorial

PROBLEM LINK:

Practice
Contest

Author: RAVIT SINGH MALIK
Editorialist: RAVIT SINGH MALIK

DIFFICULTY:

MEDIUM - HARD

PREREQUISITES:

MATHS,NUMBER THEORY

PROBLEM:

You are required to find the number of trailing $zeroes$ of F(n) = $1^{1!} \times 2^{2!} \times 3^{3!} $......$N^{N!}$ ..

EXPLANATION:

suppose you have to find the number of zeroes in a product.$ 24 \times 32 \times 23 \times 19$ = $ 2^{3} \times 3^{1} \times 2^{5} \times 23 \times 19 $ as you can notice, this product will have no zeroes because it has no 5 in it.
however, if you have expression like: $23\times39\times32\times125=2^{5}\times3\times5^{3}\times11\times23 $ Zeroes are formed by the combination of $2\times5$. Hence,the number of zeroes will depend on number of pairs of 2's and 5's that can be formed. In the above product, there are five twos and three fives.Hence, ther will be 3 Zeroes in the product.

Find the number of trailing zeroes in 101! Okay, how many multiples of 5 are there in the numbers from 1 to 101? There's 5, 10, 15, 20, 25,...

Oh, heck; let's do this the short way: 100 is the closest multiple of 5 below 101, and 100 ÷ 5 = 20, so there are twenty multiples of 5 between 1 and 101.

But wait: 25 is 5×5, so each multiple of 25 has an extra factor of 5 that I need to account for. How many multiples of 25 are between 1 and 101? Since 100 ÷ 25 = 4, there are four multiples of 25 between 1 and 101.

Adding these, I get 20 + 4 = 24 trailing zeroes in 101!

How many trailing zeroes would be found in 4617!, upon expansion? I'll apply the procedure from above:

51 : 4617 ÷ 5 = 923.4, so I get 923 factors of 5
52 : 4617 ÷ 25 = 184.68, so I get 184 additional factors of 5
53 : 4617 ÷ 125 = 36.936, so I get 36 additional factors of 5
54 : 4617 ÷ 625 = 7.3872, so I get 7 additional factors of 5
55 : 4617 ÷ 3125 = 1.47744, so I get 1 more factor of 5
56 : 4617 ÷ 15625 = 0.295488, which is less than 1, so I stop here.
Then 4617! has 923 + 184 + 36 + 7 + 1 = 1151 trailing zeroes.

In the given problem You are required to find the number of trailing zeroes of F(n) = $1^{1!} \times 2^{2!} \times 3^{3!} ......N^{N!}$ so, if n=6 hence no,of twos is $ 2!+2\times4!+2\times6! $ and no. of fives are 5! so,clearly the fives will be less than twos. Hence, we need to count only the fives. Thus: 5!=120 so,thus the f(6) has 120 trailing zeroes.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

RELATED PROBLEMS:

This question is marked "community wiki".

asked 10 Oct '16, 13:06

ravit0001's gravatar image

5★ravit0001
346
accept rate: 0%

edited 05 Jan '17, 13:19


include<math.h>

include<stdio.h>

int main(){ int t; scanf("%d",&t); int m,i,j,fact=1,f=1; for(i=1;i<=t;i++){ scanf("%d",&m); } for(j=1;j<=m;j++){ fact=factj; f=fpow(m,fact); fact=fact; printf("%d\n",f); } return 0; }

link

answered 23 Dec '17, 08:19

mani_170040607's gravatar image

1★mani_170040607
11
accept rate: 0%

edited 23 Dec '17, 08:20

include<stdio.h>

define MAX 10004

define MOD 1000000007

typedef long long ll; ll fact[1007]; int main(){ ll t; scanf("%lld",&t); fact[1]=1; fact[0]=1; for(ll i=1;i<=500;i++) fact[i]=(fact[i-1]i)%100000007; while(t--){ ll n; ll ans=0; scanf("%lld",&n); if(n-n%2<n-n%5) { ll i=2; while(i<=n) { for(ll j=i;j<=n;j+=i) { ans=(ans+fact[j])%100000007; } i=2; } } else { ll i=5; while(i<=n) { for(ll j=i;j<=n;j+=i) { ans=(ans+fact[j])%100000007; } i*=5; } } printf("%lld\n",ans); } return 0; }

link

answered 28 Dec '17, 08:17

s26170040192's gravatar image

0★s26170040192
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,679
×1,250
×631
×17
×2

question asked: 10 Oct '16, 13:06

question was seen: 1,270 times

last updated: 28 Dec '17, 08:17