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

Breaking The Summation Formula (Part 1)

 Q. f ( n ) =  - 1 + 2 - 3 + .. + ( - 1) n n .  Given n, find out f(n) Approach(1)- Bruteforce: 1. Calculation sum=n*(n+1)/2 2. loop[i=1,i=n : i+=2] odd+=i 3.ans=sum-2*odd Code: #include < bits / stdc ++. h > using namespace std ; int main (){   long long x ; cin >> x ; long long p =( x *( x + 1 ))/ 2 ; long long bad = 0 ; for ( long long i = 1 ; i <= x ; i += 2 ) bad += i ; cout << p - 2 * bad << endl ; } Approach(2)-Greedy: Basic: s=1+2+3+4+....+n Formula: sum=n*(n+1)/2= (n/2) + (n+1).2 ...
Post a Comment
Read more

Game Theory with examples

Game Theory with examples Introduction In this article I will be covering problems related to two players game in which it is assumed that both players play optimally and we have to find out the winner of the game. First we will look at the  basic   division of positions to winning and losing . Then we will see the  Game of Nim  and then see how it will be used to solve the  Composite games . Basic Division of positions to winning and losing Problem Statement:  Consider a simple game played by two players A and B . There are n stones on the table. Each player can pick 1 , 2 or 5 stones in each turn. Both players pick the stones alternately until the total number of stones left on the table is 0. The player unable to make the move will lose. Assuming that both the players play optimally, output the winner of the game. Solution:  As you can see positions 1 , 2 and 5 are winning positions since the player can pick up all the stones and other player will n...
Post a Comment
Read more

বিগেনার কম্পিটিটিভ প্রোগ্রামরদের জন্য কিছু প্রয়োজনীয় টপিকস

Competitive Programming For Beginners Topics Subtopics Time/Memory Complexity 1. Importance of calculating time/memory complexity and how to do it Basic STL (C++) 1. Vector ( insert , erase , iteration ) 2. Queue 3. Stack 4. Deque Data Structure 1. Map (C++) 2. Priority Queue (C++) 3. Set (C++) 4. Linked list using array Bitwise Operation 1. Bitwise operation (AND , OR , XOR and more) 2. Manipulation of bits 3. Some special use Math 1.Calculating GCD efficiently (Euclidean algorithm) 2.Sieve (finding prime numbers) 3.Bitwise sieve 4. Factorization 5. Modular Arithmetic ( addition , multiplication , calculating bigmod) 6. Fermat's little theorem and its use 7. Totient function 8. Combinatorics (factorials , counting problem) Sorting Algorithm 1. Bubble sort 2. Insertion sort 3. Counting sort 4. Selection sort 5. Quick sort 6. Merge sort Recursion 1. Introduction to recursion 2. Backtracking Gre...
Post a Comment
Read more