Inversion count (using maerge sort)

Inversion count

#include<bits/stdc++.h>

using namespace std;

void merg(long long int st,long long int mm,long long int en);

long long int a[10000001],b[10000001],inc=0;

void merge_sort(long long int st,long long int en)
{
  int m;
  if(en>st)
  {
   m=(st+en)/2;
   merge_sort(st,m);
   merge_sort(m+1,en);
   merg(st,m,en);
  }
}

void merg(long long int st,long long int m,long long int en)
{

 long long int f=st,k=st,sst=m+1,i;
 while(f<=m && sst<=en)
 {
   if(a[f]<a[sst])          ///sst= second start
    {b[k++]=a[f++];}
   else
    {b[k++]=a[sst++];
          if(a[f]!=a[sst])  inc=inc+(m-f+1);  ///this line makes merge sort to inversion count
    }
 }

  if(f>m)
   for(i=sst;i<=en;i++)
   b[k++]=a[i];

  else
  for(i=f;i<=m;i++)
  b[k++]=a[i];

  for(i=st;i<=en;i++)
  a[i]=b[i];
}


int main()
{
int t;
cin>>t;
 while(t--)
 {
  long long int n,i;
  cin>>n;
  inc=0;
   for(i=0;i<n;i++)
   cin>>a[i];
   merge_sort(0,n-1);
   cout<<inc<<endl;
 }
return 0;
}

a/b mod p

 =  (making use of Fermat's little theorem).

Finding how many numbers have odd number divisers in th range [a,b]

Given two number a and b.Count how many numbers in the range a to b(including both a and b) has odd number of divisors.

Input
First line of input contains number of test cases T.Each of the next T lines contains two number a and b.

Output
For each test case output a single line containing resulting count.

Constraints

T<=100
1<=a<=b<=10^12

Sample Input

1
2 5

Sample Output

1

Explanation

Divisors of 2:1,2
Divisors of 3:1,3
Divisors of 4:1,2,4
Divisors of 5:1,5
So only 4 has odd number of divisors which gives count as 1.

Solution ::

#include<stdio.h>
#include<math.h>
int main()
{
    int t;
    scanf("%d",&t); // Test cases
    while(t--)
    {
        long long a,b,ans=0;
        scanf("%lld%lld",&a,&b);
        long long first_root=ceil(sqrt(a));//sqrt of first perfect square in [a,b]
        long long last_root=sqrt(b);      //sqrt of last perfect square in [a,b]
        ans=last_root-first_root+1;
        printf("%lld\n",ans);
    }
    return 0;
}

Explanation ::

Because divisors of a number always exist in pairs, so if “i” is a divisor of a number “n“, then “n/i” would also be a divisor.
This means that the count of divisors usually remains even. The only situation where the count becomes odd is when

   i=n/i
=> i*i=n

i.e. when the number is a perfect square.

So our task becomes to count the number of perfect squares in range[a,b].

To find the perfect squares in range [a,b], we use the following :-

Largest number with square equal to or lesser than a = (int)sqrt(a)
First number with square in range[a,b],first_root = (int)sqrt(a), if a is perfect                                                                   square
                                                    (int)sqrt(a)+1, otherwise
Largest number with square equal to or lesser than b,last_root = (int)sqrt(b)
The count of numbers between first_root and last_root = last_root-first_root+1

TOTAL NUMBER OF DIVISERS OF A NUMBER not just prime by kishlay's  blog

------------------------------------------------------------------------------------------------------------------------

imp concept

to count the total number of divisor( not just prime) using the prime number for optimization , we calculate total number of times a prime divides the number and then multiply them.

for example in case of 12

the factors are , 1 ,2, 3,4,6,12              total of 6

the prime factors are 2 ( two times ) and 3 ( one time)

if we add one with the frequency and multiply them we get the total number of  factor( that are not just prime) 

ARTICULATION POINTS IN A GRAPH

articulation point is a vertex of a graph if this vertex get  out of the graph ,then the graph will get disconnected.

spoj question in articulation point http://www.spoj.com/problems/SUBMERGE/

code:-

#include<bits/stdc++.h>

using namespace std;

vector<int>a[100000];
int arr[100000],parent[100000],low[100000],visited[100000],tim=1;
set<int> s;


void dfs(int st)
{
arr[st]=tim++;
low[st]=arr[st];
visited[st]=1;

int child=0;

 for(int i=0;i<a[st].size();i++)
 {
  if(visited[a[st][i]]==0)
  {
    child++;
    parent[a[st][i]]=st;

    dfs(a[st][i]);

    ///lower part of this code starts executing for leaf

    low[st]=min(low[st],low[a[st][i]]);                  ///"low" child ke karan change ho raha hai

    if(parent[st]==INT_MAX && child>1) s.insert(st);       ///dfs root ke liye articulation ka condition
   
//cout<<st<<" is articulation point"<<endl;

    if(low[a[st][i]]>=arr[st] && parent[st]!=INT_MAX ) s.insert(st);   ///ye general
    //cout<<st<<" is articulation point"<<endl;
  }

   else if(visited[a[st][i]]==1 && parent[st]!=a[st][i])   ///ye bata raha hai backage st ka
    low[st]=min(low[st],arr[a[st][i]]);                   /// iss condition me low aise upadate hoga
                                                         ///"low" backage ke karan change ho raha hai
 }
}

int main()
{
 int i,j;
 while(1)
 {
 int v,e,p,q;
 cin>>v>>e;

 if(v==0 && e==0)
 break;

 for(i=0;i<e;i++)
 {
  cin>>p>>q;
  a[p].push_back(q);
  a[q].push_back(p);
 }
 tim=1;
  parent[1]=INT_MAX;
  dfs(1);
  cout<<s.size()<<endl;

  s.clear();
  for(i=0;i<100000;i++)
  a[i].clear();

  for(i=0;i<100000;i++)
  parent[i]=arr[i]=low[i]=visited[i]=0;
 }
return 0;
}

------------------------------------------------------------0----------------------------------------------------------------------------------------------------------------------0-----0---------------------------------------------------------------------------------------------------------------------0---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Adjacency matrix solution 

#include<bits/stdc++.h>

using namespace std;

int a[100][100],arr[1000],parent[1000],low[1000],visited[1000],tim=1,v;

void dfs(int st)

{

arr[st]=tim++;

low[st]=arr[st];

visited[st]=1;

int child=0;

 for(int i=0;i<v;i++)

 {

  if(a[st][i]==1 && visited[i]==0)

  {

    child++;

    parent[i]=st;

    dfs(i);

    ///lower part of this code starts executing for leaf

    low[st]=min(low[st],low[i]);                  ///"low" child ke karan change ho raha hai

    if(parent[st]==INT_MAX && child>1)            ///dfs root ke liye articulation ka condition

    cout<<st<<" is articulation point"<<endl;

    if(low[i]>=arr[st] && parent[st]!=INT_MAX )   ///ye general

    cout<<st<<" is articulation point"<<endl;

  }

  else if(a[st][i]==1 && visited[i]==1 && parent[st]!=i)   ///ye bata raha hai backage st ka

    low[st]=min(low[st],arr[i]);                          /// iss condition me low aise upadate hoga

                                                         ///"low" backage ke karan change ho raha hai

 }

}

int main()

{

 int i,j;

 cin>>v;

 for(i=0;i<v;i++)

  for(j=0;j<v;j++)

   cin>>a[i][j];

  parent[0]=INT_MAX;

  dfs(0);

return 0;

}