You would think this problem is very difficult because on the surface, it appears to deal with large numbers. This usually causes most people to turn their brains off and reach for a calculator.
However, it is really only dealing with remainders, and remainders of 101 no less, so the maximum number of digits in each step is 3 (4 through n=99, if you count the multiplication as a separate step).
So for any n! mod 101 where n>1, all you do is repeat this process (For n=1, the answer is 1, and for those unfamiliar with the term mod, it is short for modulus, which means take the remainder after dividing.):
i=2
result=1
while i<=n
result=result*i mod 101
So, we get:
1*2=2 mod 101=2
2*3=6 mod 101=6
6*4=24 mod 101=24
24*5=120 mod 101=19
19*6=114 mod 101=13
13*7=91 mod 101=91
91*8=728 mod 101=21
21*9=189 mod 101=88
88*10=880 mod 101=72
.
.
.
82*90=7380 mod 101=7
7*91=637 mod 101=31
31*92=2852 mod 101=24
24*93=2232 mod 101=10
10*94=940 mod 101=31
31*95=2945 mod 101=16
16*96=1536 mod 101=21
21*97=2037 mod 101=17
17*98=1666 mod 101=50
So, 98! Mod 101=50.
|
|
Posted by Joshua
on 2011-09-02 14:39:46 |
Solution
