NT Part 4: Mobius Function Part 1. The Introduction

What is mobius function? This function is notated as $\mu (n)$ . This function has lots of definitions.

However, the main definition is the following.

$\mu (n)$ is $1$ if $n=1$ or $n$ is square-free and has even number of prime divisors.
$\mu (n)$ is $-1$ if $n$ is square-free and has odd number of prime divisors.
$\mu (n)$ is $0$ if $n$ is not square-free.

$\mu (n)$ also has a lot of interesting properties that make $\mu (n)$ so important.

$\sum_{d|n} \mu (d) = 0$ for all $n>1$ , and $\mu (n)$ is multiplicative.
(A function $f$ is multiplicative if $f(mn)=f(m)f(n)$ for all $(m,n)=1$ .)

How do we calculate $\mu (n)$ 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]==1)
        {
            mu[i]=-mu[i];
            for(j=2 ; i*j<=111100 ; j++)
            {
                primechk[i*j]=0;
                if(j%i==0)
                {
                    mu[i*j]=0;  
                }   
                else
                {
                    mu[i*j]=-mu[i*j];
                }
            }   
        }   
    }
}

Okay, $O(n \log \log n)$ is good. Now, how do we use $\mu (n)$ ?

Comments

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 ...

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...

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

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...

This lifeless coder is welcoming you!

Search This Blog