Page 1 of 1
Clarification on Project Euler Problems...
Posted: Mon Apr 22, 2019 3:27 am
by kenbrooker
ok... I give up... Why are so many Project Euler problem solutions
qualified as mod (10^9 + 7 [or + 9])??
Re: Clarification on Project Euler Problems...
Posted: Mon Apr 22, 2019 7:49 am
by philiplu
They're both prime, so certain useful theorems in modular arithmetic which require either a prime or coprime modulus will work (intentionally not saying what those are - plenty of problems revolve around discovering those). Also, they're below $2^{30}$, so if you compute $a*b \pmod{1000000007}$, where $a$ and $b$ are both below the modulus, the intermediate result of the multiplication will stay below $2^{63}$ so you don't hit overflow issues when using signed or unsigned 64-bit integers. Seems like lots of problems are sized to stay within 64-bit arithmetic limits, so they're easier to handle in languages like C++ without automatic infinite-precision integers. If, say, Python, is your language of choice, that's not an issue, other than the slowdown you'll hit if your ints exceed 64 bits.
Re: Clarification on Project Euler Problems...
Posted: Mon Apr 22, 2019 5:59 pm
by kenbrooker
ThankYouSIR!