大数取模 modulo arithmetic
2024年5月18日春季美墨边境有3500位走线移民者,法院至少接受1位,至多接受全部的避难申请。请问总共有多少种接受方法?注意:该数字很大,只需要写出该数字除以
解答:
每个走线者,要么被接受要么不被接受,有2种可能。所以有
但是题目难点在计算大数除以
Modulo Arithmetic
In Euclidean division defined on integers
If we only concern the remainder r, there are two forms of modulo operations we can use, the congruent modulo and the binary modulo. The congruent modulo form
Distributive laws
- (x + y) mod m = [(x mod m) + (y mod m)] mod m
- xy mod m = [(x mod m)(y mod m)] mod m
We can derive new properties from the distributive law of mutiplication.
Similarly, we have
First use the distributive law of addition.
Then we just zero in on
Modular Exponentiation
Modular exponentiation is the form
Let’s start trying
Next, factorize 73741817.
Similarly,
To save space, use m to present
We may fastforward
- 510100431=3*617*275581
- 120048155=5*23*1043897
- 288008282=2*144004141
Round 2
Round 3
- 924113713=4127*223919
- 220703118=2*3*36783853
- 404825426=2*97*1409*1481
- 720938986=2*360469493
- 73741817=101*491*1487
- 479987537=17*131*215531
Reorganize the expression
Up to now, we have to use a computer. See Code for 大数取模 modulo arithmetic.
[…] as I talked about in the previous article, you have to do prime factorization. There is certainly room to optimize the […]