Skip to main content

NT Part 3: Playing with Modulars, and Euler Phi Function

 Quick stuff first, fast exponentiation in logarithm time.


Let us calculate $a^b$ in modular $m$ in $O(\log b)$.
It uses binary expansion of $b$, and is very very straightforward.

ll exp(ll x, ll n)  
{  
    if(n==0) return 1;  
    if(n==1) return x;  
    if(n%2==0) return exp((x*x)%mod,n/2);  
    if(n%2==1) return (x*exp((x*x)%mod,n/2))%mod;  
}


Now, let us talk about modular inverses.

By using Extended Euclidean Algorithm, we can get the inverse of $a$ modulo $m$.

#include <iostream>
int inv(int a, int m)
{
    int temp=m, q, t, u=0, v=1;
    if(m==1) return 0;
    while(a>1)
    {
        q=a/m;
        t=m;
        m=a%m;
        a=t;
        t=u;
         u=v-q*u;
         v=t;
    }
    if(v<0) v+=temp;
    return v;
}
int main(void)
{
    int a, m;
    std::cin>>a>>m;
    std::cout<<inv(a,m);
}


Of course, logarithm time. If $m$ is prime, we can do a lot of different things.

Fermat's Little Theorem gives $a^{p-1} \equiv 1 \pmod{p}$ if $(a,p)=1$, where $p$ is a prime.
Therefore, we can calculate the modular inverse of $a$ as $a^{p-2}$, by fast exponentiation.
Time Complexity is $O(\log p)$.

Also, you can get the modular inverse of all numbers in $[1,n]$ in $O(n)$.
The code for this is shown below. The proof for the correctness is left to the reader (not difficult)

#include <iostream>
typedef long long ll;
using namespace std;
int inv[111111], n;
ll mod=1e9+7;
int main(void)
{
    cin>>n;
    int i;
    inv[1]=1;
    for(i=2 ; i<=n ; i++)
    {
        inv[i]=((mod-mod/i)*inv[mod%i])%mod;
        cout<<inv[i]<<endl;
    }
}


We can also calculate $\binom{n}{m}$ in modulo $p$ ($p$ is a prime) very fast using Lucas' Theorem.

Lucas' Theorem basically states that $\binom{n}{m} \equiv \binom{n_0}{m_0} \cdot \binom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}$, where $n_0$ is $n$ modulo $p$ and $m_0$ is $m$ modulo $p$.

This is very efficient when $p$ is small and $n, m$ is huge. We can precalculate the factorials and inverse of factorials modulo $p$ by using the above code, and solve each queries in $O(\log_p \text{max} (n,m))$.

Also, we can use Chinese Remainder Theorem to solve a system of modular equations.

Let us solve $x \equiv r_i \pmod {m_i}$, where $m_i$ are pairwise coprime.
(If they are not coprime, break them into prime powers, and if some are contradictory, there are no solutions.)

The CRT itself gives an algorithm to get our answer.
Set $M= \prod_{i=1}^n m_i$, and $u_i = \frac{M}{m_i}$. Also, set $s_i$ as the modular inverse of $u_i$ in modulo $m_i$. Then our answer is $\sum_{i=1}^n r_is_iu_i \pmod{M}$

We learned how to calculate modular inverse in logarithm time above. So the time complexity is $O(n \log MAX)$.

long long int r[111111]; // remainders
long long int m[111111]; // modulars
long long int M=1; // product
int n; // number of equation
int res(void)
{
    int i;
    for(i=1 ; i<=n ; i++)
    {
        M=M*m[i];
    }
    long long int ret=0;
    for(i=1 ; i<=n ; i++)
    {
        ret+=r[i]*inv(M/m[i],m[i])*(M/m[i]);
        ret=ret%M;
    }
    return ret;
}


$\phi (n)$ is the number of positive integers no more than $n$ which is coprime with $n$.
Formula is $\phi (n) = n \prod_{p|n} (1-\frac{1}{p})$. Proof is Inclusion-Exclusion.
Also, we have the formula $\sum_{d|n} \phi (d) = n$.

Of course, for the calculation of Euler Phi numbers, we can tweak the Eratosthenes's Sieve algorithm a little bit.

void preprocess(void)
{
    int i, j;
    eulerphi[1]=1;
    for(i=2 ; i<=122000 ; i++)
    {
        eulerphi[i]=i;
        primechk[i]=1;
    }
    for(i=2 ; i<=122000 ; i++)
    {
        if(primechk[i]==1)
        {
            eulerphi[i]-=eulerphi[i]/i;
            for(j=2 ; i*j<=122000 ; j++)
            {
                primechk[i*j]=0;
                eulerphi[i*j]-=eulerphi[i*j]/i;
            }
        }
    }
}


You could also calculate $\phi (n)$ by using prime factorization of $n$.

Now let's get to the fun stuff. The mobius function.

Comments

Post a Comment

Popular posts from this blog

Big O Notation — Time & Space Complexity in Ruby!

  Big O Cheat Sheet In this post, we will look at the Big O Notation both time and space complexity! For all our examples we will be using Ruby. What is Big O Notation? Big O notation is just a fancy way of describing how your code’s performance depends on the amount of data its processing. It allows us to calculate the worst possible runtime of an algorithm, or how long it takes the algorithm to complete. In other words, it informs us of how much it will slow down based on the input size. It’s usually talked about in two ways the  time complexity ( how long an algorithm takes )and  space complexity ( how much space an algorithm uses ) Let me put this graph here we can refer to it as we go on, it’s a graph showing the complexities compare against each other. Big O complexity chart Time Complexity Before we get try wrapping our heads around the different big O notations here is a nice table that I am borrowing to show how speed will slow down based on the size of the datas...
Post a Comment
Read more

NT Part 2: Generating Primes, Prime Test, Prime Factorization

  Generating primes fast is very important in some problems. Let's cut to the chase and introduce Eratosthenes's Sieve. The main idea is the following. Suppose we want to find all primes between 2 and 50. Iterate from 2 to 50. We start with 2. Since it is not checked, it is a prime number. Now check all numbers that are multiple of    except  2. Now we move on, to number 3. It's not checked, so it is a prime number. Now check all numbers that are multiple of  ,   except  3. Now move on to 4. We see that this is checked - this is a multiple of 2! So 4 is not a prime. We continue doing this. Here's the implementation. #include <stdio.h> int primechk [ 21000 ] ;   void preprocess ( void ) { int i, j ; for ( i = 2 ; i <= 20000 ; i ++ ) { primechk [ i ] = 1 ; } for ( i = 2 ; i <= 20000 ; i ++ ) { if ( primechk [ i ] == 1 ) { for ( j = 2 ; i * j <= 20000...
Post a Comment
Read more

NT Part 6: Sieve of Eratosthenes(Details)

  About 2300 years ago from today, famous Greek mathematician Euclid proved that there are an infinite number of prime numbers. Since then people have been searching for these prime numbers. In 1849, one of the greatest mathematician of all time, Carl Fredrick Gauss, had identified almost all of the prime numbers within the first 3 hundred thousand whole numbers. In the age of computers, we can find large prime numbers in the blink of an eye. But to do that, we need to know a bit of programming and a 2000 year old algorithm. By the end of this tutorial, you will be able to figure out a solution on your own to Gauss’s problem. What is a Prime Number? A prime number is an integer number that is divisible by 1 and the number itself only. For example, 7 is divisible by 1 and 7 only. But 6 is not a prime number because 6 is be divisible by 2 and 3 as well. It is worth mentioning that 1 itself is not a prime number. Now if you are asked to determine if a number is a prime number, you can...
Post a Comment
Read more