Number Theory

/// Euler totient phi . Given n . Calculates number of coprimes <=n . 

void Totient_Phi()
{
    for(int i=1;i<N;++i)
    {
        phi[i]=i ;
    }
    for(int i=2;i<N;++i)
    {
        if(chk[i]==0) /// prime
        {
            for(int j=i;j<N;j+=i)
            {
               phi[j]=(a[j]/i)*(i-1) ;
               chk[j]=1 ;
            }
        }
    }
}

//// gives number of coprime from ( 1 to r ) w.r.t n 
int inclusion_exlcusion (int n, int r) {
    vector<int> p;
    for (int i=2; i*i<=n; ++i)
        if (n % i == 0) {
            p.push_back (i);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        p.push_back (n);

    int sum = 0;
    for (int msk=1; msk<(1<<p.size()); ++msk) {
        int mult = 1,
            bits = 0;
        for (int i=0; i<(int)p.size(); ++i)
            if (msk & (1<<i)) {
                ++bits;
                mult *= p[i];
            }

        int cur = r / mult;
        if (bits % 2 == 1)
            sum += cur;
        else
            sum -= cur;
    }

    return r - sum;
}

/// mobius function ... fun fact till now i was doing it by iterating over all divisors in nlogn but mobius can do it in every query O(n) .  
/// given a grid of size n*m .. count number of pairs such that they have a unique gcd ... ( solve lightoj ray gun ) ,, 

 fill(pr,pr+N,1) ; fill(mob,mob+N,1) ;

    for(int i=2;i<N;i++)
    {
        if(pr[i])
        {
            for(int j=i*i;j<N;j+=i*i)
            {
                mob[j]=0 ;
            }
            for(int j=i;j<N;j+=i)
            {
                mob[j]*=-1 ;
                if(j>i)
                pr[j]= 0 ;
            }
        }
    }
    
    for(int g=1;g<=n;++g)
    {
        ans+=mob[g]*(n/g)*(m/g)    ;
        //cout<<" g "<<g<<" mob "<<mob[g]<<endl ;
    }
///