Weekly Topic: Mathematics

Prime Sieve

How many primes is in the interval $[1, n]$?

Prime number is an integer that is larger than 1 and is only divisible by 1 and itself.

1. Brute Force

Check if an integer $x$ is a prime: Only need to check if $x$ is divisible by $i$ from $2$ to $\sqrt{x}$.

2. Eratosthenes Sieve

const int maxn = (int) 1e7;

bool sieve[maxn+1];

void eratoSieve()
{
    memset(sieve,true,sizeof(sieve));
    sieve[0] = false;
    sieve[1] = false;
    
    for (int i=2; i*i<=maxn; i++)
    if (sieve[i])
    {
        for (int j=i*2; j<=maxn; j+=i)
            sieve[j] = false;
    }
}

3. Linear Sieve

Fast exponentation

How to evaluate $2 ^ {n}$ $mod$ $10^9 + 7$ quickly?

$(a \times b) \% m = ((a \% m) \times (b \% m) ) \% m$

If $n \% 2 = 0$,
$2^n = ( 2^{[\frac{n}{2}]} )^2$

If $n \% 2 = 1$,
$ 2^n = ( 2^{\frac{n}{2}} )^2 \times 2 $

ll modpow(ll x, ll n, ll m)
{
    if (n == 0)
        return 1 % m;
    ll u = modpow(x, n / 2, m);
    u = (u * u) % m;
    if (n % 2 == 1)
        u = (u * x) % m;
    return u;
}

Greatest common divisor

Given two integer point $A : (x_0, y_0), B : (x_1, y_1)$, how many integer point is on the segement $AB$? ($x_0, y_0, x_1, y_1 \leq 10^9$)

The equation of the line segment is $x = x_0 + (x_1-x_0)t$ and $y = y_0 + (y_1-y_0)t$.

We can find $d = gcd(x_1-x_0,y_1-y_0)$, then the equation will become $x = x_0 + \frac{(x_1-x_0)}{d} k$ and $y=y_0 + \frac{y_1-y_0}{d} k$.

With each $k$ from $0$ to $d$, we have an integer point on the segment.

Extended Euclidean Algorithm

Fermat Little Theorem

How to evaluate $\frac{a}{b}$ $mod$ $10^9 + 7$ quickly?

If $p$ is prime, $(a^p) \% p = a$.

If $a$ is not divisible by $p$
$a^{p-1} \% p = 1$
$a^{p-2} \% p = a^{-1}$

Probablity, Combinatorics

Often associated with Dynamic programming.

Sample Problem

Some tutorials about Probability and Combinatorics
Tutorial 1
Tutorial 2

Some Annoucement…

1. First team practice on 11:15 a.m. - 16:15 a.m. on this Saturday in Lab (CS1350).
2. About weekly training
   Bud apologizes for the difficulty of the last contest :(
   Difficulty of the problems will be included.
3. Individual contests online (Codeforces, Atcoder, Codechef).
   2.5 hours, good problems for individual training.

Thanks Bud and Yi Rong for taking the notes!