We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This was a quite hard problem. In order to solve it, fb(n) must be at most log(n). We need to split base number into prime factors and precompute modulo values for every prime up to (prime^k)^5. Then for every prime factor we must calcultate fb_prime(n) mod (prime^k)^5. At the begining we must strip trailing zeroes by multiplying by proper inverses of other primes. This is a little bit tricky and requires carefull analysis. Computing the product factors thar are comprime to given prime can be computed in log(n) time using previously precomputed values mod prime^5k. Finally we must solve a system of linear congruences using Chinese Reminder Theorem.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #160: Factorial trailing digits
You are viewing a single comment's thread. Return to all comments →
This was a quite hard problem. In order to solve it, fb(n) must be at most log(n). We need to split base number into prime factors and precompute modulo values for every prime up to (prime^k)^5. Then for every prime factor we must calcultate fb_prime(n) mod (prime^k)^5. At the begining we must strip trailing zeroes by multiplying by proper inverses of other primes. This is a little bit tricky and requires carefull analysis. Computing the product factors thar are comprime to given prime can be computed in log(n) time using previously precomputed values mod prime^5k. Finally we must solve a system of linear congruences using Chinese Reminder Theorem.