2018-12-16 17:09:54 +08:00
|
|
|
# Number Theory
|
2019-01-31 12:09:46 +08:00
|
|
|
>See more details on [my blog](https://mbinary.xyz/number-theory.html)
|
2018-12-16 17:09:54 +08:00
|
|
|
|
|
|
|
|
## gcd.py
|
|
|
|
|
- gcd(a,b)
|
|
|
|
|
- xgcd(a,b): return gcd(a,b),x,y, where ax+by = gcd(a,b)
|
|
|
|
|
|
|
|
|
|
## isPrime
|
|
|
|
|
- isPrime(n): using Miller-Rabin primalrity test.
|
|
|
|
|
- primeSieve
|
|
|
|
|
|
|
|
|
|
## euler.py
|
|
|
|
|
- phi(n): euler function
|
|
|
|
|
- sigma(n): return the sum of all factors of n
|
|
|
|
|
|
|
|
|
|
## factor.py
|
|
|
|
|
- factor(n): return a list of numbers that are the factorization of n
|
|
|
|
|
|
|
|
|
|
## modulo_equation.py
|
|
|
|
|
Solving modulo equations
|
|
|
|
|
|
|
|
|
|
```python
|
|
|
|
|
solver = solve()
|
|
|
|
|
res = solver.solveLinear(3,6,9)
|
|
|
|
|
|
|
|
|
|
res = solver.solveHigh(1,8,3,11)
|
|
|
|
|
|
|
|
|
|
res = solver.solveGroup([(5,11,2),(3,8,5),(4,1,7)])
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
# Permutation
|
|
|
|
|
|
