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

×

POFACT - Editorial

PROBLEM LINK:

Practice Contest

Author: sahilarora.535

DIFFICULTY:

SIMPLE

PREREQUISITES:

None

PROBLEM:

Given a number N, output (N!)%1589540031

EXPLANATION:

Memoize all the factorials till 10^5 before the test cases and store them in an array Fact. Then directly print Fact(N). Program Complexity = O(T*1), i.e. O(T), where T is the number of test case.

ALTERNATIVE SOLUTION:

There was this alternate solution which could be deciphered by looking at the number mod, which was equal to 1589540031 = (3^13)*997. So basically, even by naive approach, one needed to find the modulo only upto 996!, because after that, the factorial would be completely divisible by the mod, and hence the answer would be 0.

Program Complexity = O(T*997), which would pass in 1 second.

AUTHOR'S SOLUTIONS:

Solution 1(by method 1 - memoization) - here.

Solution 2(by alternative method) - here

This question is marked "community wiki".

asked 08 Apr '16, 15:33

sahilarora.535's gravatar image

4★sahilarora.535
1235
accept rate: 0%

edited 11 Apr '16, 15:20

admin's gravatar image

0★admin ♦♦
19.8k350498541


simple yet tricky question !! keep doing... :D

link

answered 08 Apr '16, 16:36

radeonguy's gravatar image

1★radeonguy
1449
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,852
×1,191
×14
×3

question asked: 08 Apr '16, 15:33

question was seen: 1,051 times

last updated: 11 Apr '16, 15:20