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

NT Part 1:GCD, LCM, Euclidean Algorithm

  The definitions of GCD and LCM are well-known, (and taught in middle school I think) I will skip the definitions. Also, since  ,  calculating GCD is equivalent to calculating LCM. Now, how do we calculate the GCD of two numbers? A naive solution would be iterating over all positive integers no more than  . This will get the GCD in  ,  very very slow. We can calculate the GCD of   in   using Euclidean Algorithm. This algorithm uses the easy-to-prove fact  ,  where   is the remainder when   is divided by  ,  or just a%b. We can now use the following code. #include <iostream> using namespace std ; int gcd ( int u, int v ) { return u % v == 0 ? v : gcd ( v,u % v ) ; } int main ( void ) { int x, y ; cin >> x >> y ; cout << gcd ( x,y ) ; } How do we prove that this algorithm is  ?  Well, let's suppose that we started with  . Then...
Post a Comment
Read more

NT Part 4: Mobius Function Part 1. The Introduction

  What is mobius function? This function is notated as  .  This function has lots of definitions. However, the main definition is the following.  is   if   or   is square-free and has even number of prime divisors.  is   if   is square-free and has odd number of prime divisors.  is   if   is not square-free.  also has a lot of interesting properties that make   so important.  for all  ,  and   is multiplicative. (A function   is multiplicative if   for all  . ) How do we calculate   fast? Again, we can tweak the Eratosthenes's Sieve a little bit. void preprocess ( void ) { int i, j ; for ( i = 1 ; i <= 111100 ; i ++ ) { mu [ i ] = 1 ; primechk [ i ] = 1 ; } primechk [ 1 ] = 0 ; for ( i = 2 ; i <= 111100 ; i ++ ) { if ( primechk [ i ] == ...
Post a Comment
Read more

NT Part 5: Mobius Function Part 2. Mobius Inversion, Dirichlet Convolution

  Theorem.  Let   be arithmetic function such that  .  Then,  . Proof. using   for all   and  . The Dirichlet Convolution of two function   is the following. Denote   as the constant function,  .  is a function which satisfies   and   for  .  is the identity function,  The mobius inversion formula and the basic property of mobius functions give  ,  and  Okay. So what? How can we use this formula to  improve our lives  solve problems? We can, change our "sum" or our answer using mobius inversion and mobius functions to calculate them fast. I will give 3 examples which changes the desired sum by using number theory (like mobius function) to calculate them fast. Example Problems Problem 1.  http://www.spoj.com/problems/LCMSUM/ Let   be the answer when  . Precalculate  ,  and add   to every  . ...
Post a Comment
Read more