Transcript Mathematics in OI

Mathematics in OI
Prepared by Ivan Li
Mathematics in OI
A brief content
•
•
•
•
•
•
•
•
•
•
•
•
•
Greatest Common Divisor
Modular Arithmetic
Finding Primes
Floating Point Arithmetic
High Precision Arithmetic
Partial Sum and Difference
Euler Phi function
Fibonacci Sequence and Recurrence
Twelvefold ways
Combinations and Lucas Theorem
Catalan Numbers
Using Correspondence
Josephus Problem
Greatest Common Divisor
• Motivation
– Sometimes we want “k divides m”
and “k divides n” occur
simultaneously.
– And we want to merge the two
statements into one equivalent
statement: “k divides ?”
Greatest Common Divisor
• Definition
– The greatest natural number
dividing both n and m
– A natural number k dividing both
n and m, such that for each
natural number h dividing both n
and m, we have k divisible by h.
Greatest Common Divisor
• How to find it?
– Check each natural number not
greater than m and n if it divides
both m and n. Then select the
greatest one.
– Euclidean Algorithm
Euclidean Algorithm
• Assume m > n
GCD(m,n)
While n > 0
m = m mod n
swap m and n
Return m
Greatest Common Divisor
• What if we want the greatest
number which divides n1,n2, …,
nm-1 and nm?
• Apply GCD two-by-two
• gcd(n1,n2, …,nm)
= gcd(n1,gcd(n2,gcd(n3,…gcd(nm-1,nm)…))
Applications
• Simplifying a fraction m/n
• If gcd(m,n) > 1, then the fraction
can be simplified by dividing
gcd(m,n) on the numerator and
the denominator.
Applications
• Solve mx + ny = a for integers x
and y
• Can be solved if and only if a is
divisible by gcd(m,n)
Least Common Multiple
• Definition
– The least natural number divisible
by both n and m
– A natural number k divisible by
both n and m, such that for each
natural number h divisible by both
n and m, we have k divides h.
• Formula
– lcm(m,n) = mn/gcd(m,n)
Least Common Multiple
• What if we want to find the LCM
of more than two numbers?
• Apply LCM two-by-two?
Extended Euclidean
Algorithm
• The table method
• e.g. solve 93x + 27y = 6
Coeff of 93
Coeff of 27
(1)
93
1
0
(2)
27
0
1
(3): (1)-3(2)
12
1
-3
(4): (2)-2(3)
3 (gcd,
3*2=6)
-2 (x = -4)
7 (y = 14)
(5): (3)-4(4)
0
9
-31
• General form:
• x = -4 + 9k, y = 14 - 31k, k integer
Modular Arithmetic
• Divide 7 by 3
• Quotient = 2, Remainder = 1
• 7 ÷ 3 = 2...1
• In modular arithmetic
• 7 ≡ 1 (mod 3)
• a ≡ b (mod m) if a = km + b for
an integer k
Modular Arithmetic
• Like the equal sign
• Addition / subtraction on both
sides
• 7 ≡ 1 (mod 3) => 7+2≡1+2 (mod 3)
• Multiplication on both side
• 7 ≡ 1 (mod 3) => 7*2≡1*2 (mod 3)
• We can multiply into m too
• 7≡1 (mod 3)<=>7*2≡1*2 (mod 3*2)
• Congruence in mod 6 is stronger
than that in mod 3
Modular Arithmetic
• Division?
• Careful:
• 6≡4 (mod 2), but not 3≡2 (mod 2)
• ac≡bc (mod m)<=>a≡b (mod m)
when c, m coprime (gcd = 1)
• Not coprime?
• ac≡bc(mod cm)<=>a≡b(mod m)
• ac ≡ bc(mod m)
<=> a ≡ b (mod m/gcd(c,m))
Modular Inverse
• Given a, find b such that
ab ≡ 1 (mod m)
• Write b as a-1
• We can use it to do “division”
• ax ≡ c (mod m)=> x ≡ a-1c (mod m)
• Exist if and only if a and m are
coprime (gcd = 1)
• When m is prime, inverse exists
for a not congruent to 0
Modular Inverse
• ab ≡ 1 (mod m)
• ab + km = 1
• Extended Euclidean algorithm
CAUTION!!!
• The mod operator “%” does not
always give a non-negative
integer below the divisor
• The answer is negative when the
dividend is negative
• Use ((a % b)+b)%b
Definition of Prime
Numbers
An integer p greater than 1 such
that:
1. p has factors 1 and p only?
2. If p = ab, a  b, then a = 1 and
b=p?
3. If p divides ab, then p divides a
or p divides b ?
4. p divides (p - 1)! + 1 ?
Test for a prime number
• By Property 1
• For each integer greater than 1
and less than p, check if it divides
p
• Actually we need only to check
integers not greater than sqrt(p)
(Why?)
Finding Prime Numbers
• For each integer, check if it is a
prime
• Prime List
• Sieve of Eratosthenes
Prime List
• Stores a list of prime numbers
found
• For each integer, check if it is
divisible by any of the prime
numbers found
• If not, then it is a prime. Add it
to the list.
Sieve of Eratosthenes
• Stores an array of Boolean
values Comp[i] which indicates
whether i is a known composite
number
Sieve of Eratosthenes
for i = 2 … n
If not Comp[i]
output i
j = i *i
while j  n
//why i*i?
Comp[j] = true
j=j+i
Optimization
• Consider odd numbers only
• Do not forget to add 2, the only
even prime
Other usages of sieve
• Prime factorization
• When we mark an integer as
composite, store the current
prime divisor
• For each integer, we can get a
prime divisor instantly
• Get the factorization recursively
Floating point arithmetic
•
•
•
•
Pascal: real, single, double
C/C++: float, double
Sign, exponent, mantissa
Floating point error
• 0.2 * 5.0 == 1.0 ?
• 0.2 * 0.2 * 25.0 == 1.0?
Floating point arithmetic
• To tolerate some floating point
• Introduce epsilon
• EPS = 1e-8 to 1e-11
• a < b => a + EPS < b
• a <= b => a <= b + EPS
• a == b => abs(a - b) <= EPS
Floating point arithmetic
• Special values
• Positive / Negative infinity
• Not a number (NaN)
• Checked in C++ by x!=x
• Denormal number
High Precision Arithmetic
• 32-bit signed integer:
-2147483648 … 2147483647
• 64-bit signed integer:
-9223372036854775808 … 9223372036854775807
• How to store a 100 digit number?
High Precision Arithmetic
• Use an array to store the digits
of the number
• Operations:
•
•
•
•
Comparison
Addition / Subtraction
Multiplication
Division and remainder
High Precision Division
• Locate the position of the first
digit of the quotient
• For each digit of the quotient
(starting from the first digit), find
its value by binary search.
High Precision Arithmetic
• How to select the base?
• Power of 2 : Saves memory
• Power of 10 : Easier input / output
• 1000 or 10000 for 16-bit integer
array
• Beware of carry
More on HPA
• How to store
• negative numbers?
• fractions?
• floating-point numbers?
Partial Sum
• Motivation
• How to find the sum of the 3rd to the
6th element of an array a[i] ?
• a[3] + a[4] + a[5] + a[6]
• How to find the sum of the 1000th to
the 10000th element?
• A for-loop will take much time
• In order to find the sum of a range
in an array efficiently, we need to
do some preprocessing.
Partial Sum
• Use an array s[i] to store the
sum of the first i elements.
• s[i] = a[1] + a[2] + … + a[i]
• The sum of the j th element to
the k th element = s[k] – s[j-1]
• We usually set s[0] = 0
Partial Sum
• How to compute s[i] ?
• During input
s[0] = 0
for i = 1 to n
input a[i]
s[i] = s[i-1] + a[i]
Difference operation
• Motivation
• How to increment the 3rd to the 6th
element of an array a[i] ?
• a[3]++, a[4]++, a[5]++, a[6]++
• How to increment the 1000th to the
10000th element?
• A for-loop will take much time
• In order to increment(or add an
arbitrary value to) a range of
elements in an array efficiently,
we will use a special method to
store the array.
Difference operation
• Use an array d[i] to store the
difference between a[i] and a[i1].
• d[i] = a[i] - a[i-1]
• When the the j th element to the
k th element is incremented,
• d[j] ++, d[k+1] - -
• We usually set d[1] = a[1]
Difference operation
• Easy to compute d[i]
• But how to convert it back to a[i]?
• Before (or during) output
a[0] = 0
for i = 1 to n
a[i] = a[i-1] + d[i]
output a[i]
• Quite similar to partial sum, isn’t it?
Relation between the two
methods
• They are “inverse” of each other
• Denote the partial sum of a by a
• Denote the difference of a by a
• The difference operator
• We have
(a) = (a) = a
Comparison
• Partial sum - Fast sum of range
query
• Difference - Fast range
increment
• Ordinary array - Fast query and
increment on single element
Runtime Comparison
Range
Query
Single
Query
Single
Update
Range
Update
Partial sum
Constant
Constant
Linear
Linear
Ordinary
array
Linear
Constant
Constant
Linear
Difference
Linear
Linear
Constant
Constant
(Convert it
back to the
original
array)
(treat a
single
element as
a range)
(Have to
update all
sums
involved)
• Does there exist a method to
perform range query and range
update in constant time?
• No, but there is a data structure
that performs the two
operations pretty fast.
Euler Phi Function
• (n) = number of integers in
1...n that are relatively prime to
n
• (p) = p-1
• (pn) = (p-1)pn-1 = pn(1-1/p)
• Multiplicative property:
(mn)=(m)(n) for (m,n)=1
• (n) = np|n(1-1/p)
Euler Phi Function
• Euler Theorem
• a(n)  1 (mod n) for (a, n) = 1
• Then we can find modular
inverse
• aa(n)-1  1 (mod n)
• a-1  a(n)-1
Fibonacci Number
•
•
•
•
F0 = 0, F1 = 1
Fn = Fn-1 + Fn-2 for n > 1
The number of rabbits
The number of ways to go
upstairs
• How to calculate Fn?
What any half-wit can do
• F0 = 0; F1 = 1;
for i = 2 . . . n
Fi = Fi-1 + Fi-2;
return Fn;
• Time Complexity: O(n)
• Memory Complexity: O(n)
What a normal person
would do
• a = 0; b = 1;
for i = 2 . . . N
t = b;
b += a;
a = t;
return b;
• Time Complexity: O(n)
• Memory Complexity: O(1)
What a Math student
would do
• Generating Function
• G(x) = F0 + F1 x + F2 x2 +. . .
• A generating function uniquely
determines a sequence (if it
exists)
• Fn = dnG(x)/dxn (0)
• A powerful (but tedious) tool in
solving recurrence
All the tedious works
G(x)
= F0 + F1 x + F2 x2 + F3 x3 +. . .
xG(x)
=
F0 x + F1 x2 + F2 x3 +. . .
x2G(x)
=
F0 x2 + F1 x3 +. . .
G(x) - xG(x) - x2G(x) = F0 +F1 x - F0 x = x
G(x) = x / (1 - x - x2)
Let a = (-1 - sqrt(5)) / 2, b = (-1 + sqrt(5)) / 2
By Partial Fraction:
G(x) = ((5 + sqrt(5)) / 10) / (a-x)+((5 - sqrt(5)) / 10) / (b-x)
= -(sqrt(5) / 5) / (1- x/a) + (sqrt(5) / 5) / (1- x/b)
• Note that 1 + rx + r2x2 +. . . = 1 / (1 - rx)
G(x) = (sqrt(5) / 5)(-1-x/a-x2/a2-...+1+x/b+x2/b2+...)
• By Uniqueness, Fn = (sqrt(5) / 5)(-1/an + 1/bn)
•
•
•
•
•
•
•
Shortcut
•
•
•
•
Characteristic Equation
Fn - Fn-1 - Fn-2 = 0
f(x) = x2 – x – 1
Then Fn = Aan + Bbn
for some constants A, B
where a, b are roots of f(x)
However
• How to compute ((-1-sqrt(5))/2)n ?
• The result must be a whole
number, but the intermediate
values may not
• Use floating point numbers
• Precision problem?
• If we are asked to find Fn mod m?
What a programmer
would do
• Note that
( )( ) = ( )
0 1
1 1
• Then
(
0 1
1 1
Fn
Fn+1
Fn+1
Fn+2
F
n
)(
0
F1
)=( )
Fn
Fn+1
• Matrix Exponential
Just like fast exponential
Twelvefold ways
• Put n balls into m boxes
• How many ways?
•
•
•
•
Balls identical / distinct?
Boxes identical / distinct?
Allow empty boxes?
Allow two balls in one boxes?
Twelvefold ways
Combinations
• The number of ways to choose r
objects among n different
objects (without order)
• nCr = n!/r!(n-r)!
Combinations
•
•
•
•
How to calculate nCr?
Calculate n!, r!, (n-r)! ?
Note nCr = n(n-1)...(n-r+1)/r!
nCr = 1;
for i = n-r+1 . . . n nCr *= i;
for i = 1 . . . r nCr /= i;
Combinations
• Overflow problem?
• Note nCr = (n/r)(n-1)C(r-1)
• nCr = 1; //that is (n-r)C0
for i = 1 . . . r
nCr *= (n - r + i);
nCr /= i;
Combinations
• What if we are asked to find
nCr mod p for very large n, r?
• Lucas Theorem
• Let
n = nknk-1...n1n0 (base p)
r = rkrk-1...r1r0
• Then
nCr  (nkCrk)(nk-1Crk-1)...(n0Cr0) (mod p)
• Works only for prime p
Combinations
• When p is large (larger than r),
computing niCri may be difficult
• (nCr)(r!) = n(n-1)...(n-r+1)
• nCrn(n-1)...(n-r+1)(r!)-1 (mod p)
where (r!)((r!)-1)  1 (mod p)
• Fermat Little Theorem gives
(r!)-1  (r!)p-2 (mod p)
Combinations
• When we are asked to mod a
square-free number, factorize it
into primes
• The situation becomes
complicated when the number
is not square-free
• Store the prime factorization of
numerator and denominator
A drunken man
• A drunken man was standing
beside a wall. On each second
he moves left or right by 1m at
random.
• What is the probability that he
returns to the original position in
k seconds without hitting the
wall?
Observations
• If k is odd, then it is impossible
Let k = 2n
• If the man returns to original
position, then there are n left and
n right moves
• Number of possible outcomes
= 22n
• We have to find the number of
moving sequence such that the
man returns to original position
without hitting the wall
Observations
• If the wall is removed, the
number of ways is 2n C n
• Let An be the number of ways
• If the first time the man returns
to his original position is at the
2ith second
• Note that the first move must be
rightward, and the 2ith move must
be leftward
Observations
• Also in the 2i - 2 seconds after the
first, he cannot return to his
original position
• Think of an invisible wall on his
original position
• Ai-1 ways for the first 2i seconds
• An-i ways for the remaining 2n-2i
seconds (may return to original
position again)
• An = i = 1...nAi-1An-i
Tedious works again
• Again, generating function
• g(x) = n=0,1,... Anxn
• g(x)2 = n=0,1,...i=0...n Ai An-i xn
= n=0,1,...An+1xn
• g(x) = A0+ xn=1,... Anxn-1
= 1 + xg(x)2
• xg(x) = (1-sqrt(1-4x))/2 or
(1+sqrt(1-4x))/2 (rejected since
xg(x)=0 when x = 0)
• Power series......
A much more elegant
approach
• We now remove the wall and note
when the man arrives at the
position 1m on the left of the
original position (If the man never
arrives at it, he won’t hit the wall)
• When he arrives at the considered
position on the first time, flip his
remaining moves, i.e. left to right,
right to left
• He will now end at the position 2m
on the left of the original position
A much more elegant
approach
• Wall removed: 2n C n ways
• End at 2m on the left of original
position: 2n C n-1 ways
• Therefore the number of ways
that the man never arrives at
the considered position is
(2nCn) – (2nCn-1)
= (2nCn)/(n+1)
• This is called Catalan Number
Applications of Catalan
Numbers
• The number of valid string
consisting of n pairs of
parenthesis
()()(), (())(), ()(()), (()()), ((()))
• The number of binary trees with
n nodes
An evil game
• N people in a circle
• Kill the first person, skip the
next k people, then kill the next,
etc.
• Josephus Problem
N = 8, k = 2
0
7
1
6
2
3
5
4
N = 8, k = 2
0
7
1
6
2
3
5
4
N = 8, k = 2
0
7
1
6
2
3
5
4
N = 8, k = 2
0
7
1
6
2
3
5
4
N = 8, k = 2
0
7
1
6
2
3
5
4
N = 8, k = 2
0
7
1
6
2
3
5
4
N = 8, k = 2
0
7
1
6
2
3
5
4
N = 8, k = 2
0
7
1
6
2
3
5
4
Josephus problem
• Closed form for k = 2
Josephus problem
• Naive simulation
• O(nk)
• With little technique in handling
the index
• O(n)
• f(n, k) = (f(n-1, k) + k) mod n
Josephus problem
• With some more little technique
in handling the index
• O(k log n)
Question?