number of numbers devisible by atleast 1 number(IEP)

Mehta and the Typical Supermarket()number of numbers devisible by atleast 1 number

Mehta is a very rich guy. He has  types of coins, and each type of coin is available in an unlimited supply.

So Mehta goes to a supermarket to buy monthly groceries. There he sees that every item has a unique price, that is, no two items have the same price.

Now, the supermarket owner tells Mehta that they are selling items in the price range  only on that particular day. He also tells Mehta that for every price, there is an item in the shop.

The supermarket has recently adopted a weird new tradition: Mehta may only use a single type of coin for each item he purchases. For example, he could pay for an item of price 4 with two 2-coins, but not with a 3-coin and a 1-coin.

As you know Mehta is very weak at calculations, so he wants you to do these calculations for him and tell how many different types of items he can buy.

Input Format 
The first line of input contains , the number of types of coins Mehta has. 
Then the next  lines contain an integer each: the ith line contains , the value of Mehta's ith type of coin.

Then the next line contains a number , the number of days Mehta goes shopping. 
Then each of the next  lines contains numbers  and , denoting that they are selling items in price range  on that particular day.

Output format 
There will be  lines, each containing the number of distinct items that can be bought at that particular day.

Constraints 
 
 
 

Sample Input

4
2
3
4
5
3
1 10
2 20
3 7

Sample output

8
14
4

Explanation 
For  and  you can buy items of price . 
For  and  you can buy items of price . 
For  and  you can buy items of price .

=========================editorial=========================

The problem boils down to counting the numbers in range  divisible by any of the given 's.

Let's define  as the count of numbers in the range  that are divisible by .

First, let's say we only have two numbers in the array, say , and we have to count the numbers in the range  which are divisible by  or . The answer to this case is:

We simply have to calculate the number of multiples of , and , but subtract the number of those which are counted twice.

Similarly, if we have three numbers, say , then the answer is:

The subtracted terms are for those which are counted twice in the first three terms, and the last term is for those which have been eliminated completely by the others.
Continuing with this reasoning, we find that the final answer for the array  is:

This is called the principle of inclusion-exclusion.

Now, let's take a look at how to calculate . First, take a look at  and .

 is simply equal to , because every number divisible by  and  is divisible by , and vice versa. This is because the least common multiple (LCM) of  and  is . Similarly, , because  is the LCM of ,  and . In general, we have:

So we have reduced  to calculating  with a single argument, .

Notice that for , we have , because any integer in  is either in  or , and vice versa. Therefore,

and

so we have reduced  to calculating , which is the number integers less than or equal to  that are divisible by . But the latter is simply , because the multiples of  less than or equal to  are . Therefore, we have: 

Now, since we have been given queries, we can simply precompute all the possible subsets along with their bitcount modulo , and perform the required calculations as mentioned above for all given queries.

Take a look at the code to get the complete insight on how to implement the above-mentioned algorithm. 

==========================================================

#include<bits/stdc++.h>

typedef long long int lli;

using namespace std;

lli arr[20];

vector<pair<int,lli> > v;

#define INF 2000000000000000000LL

long long trunc_mul(long long a, long long b)

{

    return a <= INF / b ? a * b : INF;

}

void precompute(int maxi,int n)

{

     //cout<<"maxi "<<maxi<<endl;

for(int i=1;i<maxi;i++)

     {

      int bc=0;

      lli gc=1;

      for(int j=0;j<n;j++)

       {

        if(i &(1<<j))

           {

              bc+=1;

         gc=trunc_mul(arr[j]/(__gcd(gc,arr[j])),gc);

}

 }

//  cout<<"bc "<<bc<<" gc "<<gc<<endl;

 v.push_back({bc,gc});

}

}

int main()

{

  int n,t;

  cin>>n;

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

  {

  cin>>arr[i];

  }

  int maxi=(1<<n);

  precompute(maxi,n);

  cin>>t;

  while(t--)

  {

   lli l,r;

   cin>>l>>r;

   lli ans=0;

   for(int i=1;i<maxi;i++)

     {

      int bc=v[i-1].first;

      lli gc=v[i-1].second;

lli cov=r/gc-((l-1)/gc);

if(bc%2==1) ans+=cov;

else ans-=cov;    

}

printf("%lld\n",ans);

 

  }

}