# Divisibility

### Problem Statement :

```Two positive integers P and S  are given.
is decimal representation of integer .
Lets define .

For example, if :

For each query you will be given two integers  and  that define a substring equal to .
Divisibility of given substring is equal to number of  pairs such that:
and
is divisible by , assuming that  is divisible by any other integer.

Timelimits

Timelimits for this challenge is given here

Input Format

First line contains two integers  and  separated by a single space.  is the number of queries.
Second line contains a big integer .
Next  lines contains two integers  and  separated by a single space each - begin and end points of substring.

Constraints

2  <=   P  <=  10^9
1000  <=  S  <=  10^100000
1  <=   Q  <=   100 000
1  <=  b  <=  e  <=  N

Output Format

Output Q  lines, the i-th line of the output should contain single integer  divisibility of the i-th query substring.```

### Solution :

```                            ```Solution in C :

In    C++  :

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

typedef long long int Lint;
typedef pair <int,int> ii;
int N,Q,K,srt[110000],sizeLeft[110000],
sizeRight[110000],A,B,C,D=1,R[110000][35],
L[110000][35],OK[110000];
Lint num[110000],ans[110000],G[110000],
P,POW[35]; //G[x]=f( x , N )
ii query[110000];
string s;

int compare( const int &a , const int &b ){
if( query[a].fi/K != query[b].fi/K )
return query[a].fi < query[b].fi;
return query[a].se < query[b].se;
}

int compare2( const int &a , const int &b )
{ return G[a] < G[b]; }

int main(){

cin >> P >> Q;
cin >> s;
while( (P%2) == 0 ){ P/=2; A++; D*=2; }
while( (P%5) == 0 ){ P/=5; B++; D*=5; }
C=max( A , B );
N=s.size();
for( int i=0 ; i<N ; i++ ) num[i+1]=s[i]-'0';
K=sqrt( N );

Lint power=1;
for( int i=N ; i ; i-- ){
srt[i+1]=i+1;
G[i]=(G[i+1]+(power*num[i])%P)%P;
power=(power*10LL)%P;
}
POW[0]=1;
for( int i=1 ; i<=32 ; i++ ) POW[i]=(POW[i-1]*10)%D;
srt[1]=1;

sort( srt+1 , srt+2+N , compare2 );

for( int i=1,prev=-1,count=0 ; i<=N+1 ; i++ ){
if( G[srt[i]] !=prev  ) count++,prev=G[srt[i]];
G[srt[i]]=count;
}

for( int i=1 ; i<=N ; i++ ){
Lint md=0;
int j;
for( j=0 ; i-j && j<C ; j++ ){
md=(md+(POW[j]*num[i-j])%D)%D;
R[i+1][j+1]=R[i+1][j];
if( !md && G[i-j] == G[i+1] )
R[i+1][j+1]++,L[i-j][j+1]++;
}
if( j == C && !md ) OK[i+1]=1;
}

for( int i=1 ; i<=N+1 ; i++ )
for( int j=0 ; i+j<=N && j<C ; j++ )
L[i][j+1]+=L[i][j];

for( int i=1,begin,end ; i<=Q ; i++ ){
scanf(" %d %d",&begin,&end);
query[i]=ii( begin , end );
srt[i]=i;
}
sort( srt+1 , srt+1+Q , compare );

Lint sum=0;
int left=N,right=N+5,r,l;

for( int i=1,b,e ; i<=Q ; i++ ){
b=query[srt[i]].fi,e=query[srt[i]].se+1;

if( e < right ){
r=b-C-1,l=b+C;
memset( sizeRight , 0 , sizeof sizeRight );
memset( sizeLeft , 0 , sizeof sizeLeft );
left=b,right=b-1;
sum=0;
}
for( int j=right+1 ; j<=e ; j++ , r++ ){
if( r >= left ) sizeRight[G[r]]++;
if( j-left > C && OK[j] ) sum+=
sizeRight[G[j]],sizeLeft[G[j]]++;
sum+=R[j][min(j-left,C)];
}
for( int j=left-1 ; j>=b ; j-- , l-- ){
if( OK[l] && l <= e ) sizeLeft[G[l]]++;
sum+=sizeLeft[G[j]]+L[j][min(C,e-j)];
if( e-C > j ) sizeRight[G[j]]++;
}
for( int j=left ; j<b ; j++  ){
if( l < e ){
l++;
sum-=sizeLeft[G[j]]+L[j][min(C,e-j)];
if( OK[l] ) sizeLeft[G[l]]--;
}else sum-=L[j][e-j];
if( l >= e ) l=j+C+1;
if( e-C > j ) sizeRight[G[j]]--;
}
left=b; right=e;
ans[srt[i]]=sum;
}

for( int i=1 ; i<=Q ; i++ ) printf("%lld\n",ans[i]);

return 0;

}

In    C :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define HASH_SIZE 123455
typedef struct _node{
int x;
int c;
struct _node *next;
} node;
void QQ(int x,int y);
void remove_left(int X);
void remove_right(int X);
void sort_a3(int*a,int*b,int*c,int size);
void merge3(int*a,int*left_a,int*right_a,int*b,
int*left_b,int*right_b,int*c,int*left_c,int*right_c,
int left_size,int right_size);
void insert(node **hash,int x);
void removee(node **hash,int x);
int count(node **hash,int x);
node *get();
void free_node(node *x);
char S[100001];
int cl,cr,a[100001],q1[100000],q2[100000],
y[100000],idx[100000],g1[100000][30],g2[100000]={0},
g3[100000][30],x;
long long ans[100000],tans;
node *hash1[HASH_SIZE]={0},*hash2[HASH_SIZE]={0},

int main(){
int P,Q,N,P1,i,j;
long long t,t1;
for(i=0;i<200000;i++)
if(i!=200000-1)
pool[i].next=&pool[i+1];
else
pool[i].next=NULL;
scanf("%d%d%s",&P,&Q,S);
N=strlen(S);
for(i=0;i<Q;i++){
scanf("%d%d",q1+i,q2+i);
q1[i]--;
q2[i]--;
}
for(i=0,x=(int)sqrt(N);i<Q;i++){
a[i]=q1[i]/x;
y[i]=q2[i];
idx[i]=i;
}
sort_a3(a,y,idx,Q);
for(x=0,P1=1;P%2==0;){
P/=2;
P1*=2;
x++;
}
for(t=0;P%5==0;){
P/=5;
P1*=5;
t++;
}
x=(x>t)?x:t;
for(i=N-1,t=1;i>=0;i--,t=t*10%P)
if(i==N-1)
a[i]=(S[i]-'0')%P;
else
a[i]=(a[i+1]+(S[i]-'0')*t)%P;
a[N]=0;
if(!x)
for(i=0;i<N;i++)
g2[i]=1;
else{
for(i=0;i<N;i++)
for(t=0,t1=1,j=0;j<x && i-j>=0;j++,t1*=10){
t=t+(S[i-j]-'0')*t1;
if(!j)
if(t%(P1*P)==0)
g1[i][j]=1;
else
g1[i][j]=0;
else
if(t%(P1*P)==0)
g1[i][j]=g1[i][j-1]+1;
else
g1[i][j]=g1[i][j-1];
}
for(i=x-1;i<N;i++){
for(t=0,j=i-x+1;j<i+1;j++)
t=t*10+S[j]-'0';
if(t%P1==0)
g2[i]=1;
}
for(i=0;i<N;i++)
for(t=0,j=0;j<x && i+j<N;j++){
t=t*10+(S[i+j]-'0');
if(!j)
if(t%(P1*P)==0)
g3[i][j]=1;
else
g3[i][j]=0;
else
if(t%(P1*P)==0)
g3[i][j]=g3[i][j-1]+1;
else
g3[i][j]=g3[i][j-1];
}
}
for(i=cl=cr=0,tans=0;i<Q;i++){
QQ(q1[idx[i]],q2[idx[i]]);
ans[idx[i]]=tans;
}
for(i=0;i<Q;i++)
printf("%lld\n",ans[i]);
return 0;
}
void QQ(int x,int y){
while(cl<x)
remove_left(cl++);
while(cl>x)
while(cr<y+1)
while(cr>y+1)
remove_right(--cr);
return;
}
if(X>=cr)
return;
if(X+x<cr){
insert(hash1,a[X]);
if(g2[X+x])
insert(hash2,a[X+x+1]);
tans+=count(hash2,a[X]);
if(x)
tans+=g3[X][x-1];
}
else
tans+=g3[X][cr-X-1];
return;
}
if(X<cl)
return;
if(X-x>=cl){
insert(hash1,a[X-x]);
if(g2[X]){
insert(hash2,a[X+1]);
tans+=count(hash1,a[X+1]);
}
if(x)
tans+=g1[X][x-1];
}
else
tans+=g1[X][X-cl];
return;
}
void remove_left(int X){
if(X>=cr)
return;
if(X+x<cr){
removee(hash1,a[X]);
tans-=count(hash2,a[X]);
if(g2[X+x])
removee(hash2,a[X+x+1]);
if(x)
tans-=g3[X][x-1];
}
else
tans-=g3[X][cr-X-1];
return;
}
void remove_right(int X){
if(X<cl)
return;
if(X-x>=cl){
if(g2[X]){
tans-=count(hash1,a[X+1]);
removee(hash2,a[X+1]);
}
if(x)
tans-=g1[X][x-1];
removee(hash1,a[X-x]);
}
else
tans-=g1[X][X-cl];
return;
}
void sort_a3(int*a,int*b,int*c,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left_a,*left_b,*left_c,*right_a,*right_b,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
right_c[i]=c[i+m];
}
sort_a3(left_a,left_b,left_c,m);
sort_a3(right_a,right_b,right_c,size-m);
merge3(a,left_a,right_a,b,left_b,right_b,c,
left_c,right_c,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
free(left_c);
free(right_c);
return;
}
void merge3(int*a,int*left_a,int*right_a,
int*b,int*left_b,int*right_b,int*c,
int*left_c,int*right_c,int left_size,
int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else if (left_a[i] == right_a[j]) {
if(left_b[i]<=right_b[j]){
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
}
else{
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
} else if (left_a[i] < right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
c[i+j] = left_c[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
c[i+j] = right_c[j];
j++;
}
}
return;
}
void insert(node **hash,int x){
node *t=hash[x%HASH_SIZE];
while(t){
if(t->x==x){
t->c++;
return;
}
t=t->next;
}
t=get();
t->x=x;
t->c=1;
t->next=hash[x%HASH_SIZE];
hash[x%HASH_SIZE]=t;
return;
}
void removee(node **hash,int x){
node *t=hash[x%HASH_SIZE],*p=NULL;
while(t){
if(t->x==x){
t->c--;
return;
}
p=t;
t=t->next;
}
return;
}
int count(node **hash,int x){
node *t=hash[x%HASH_SIZE];
while(t){
if(t->x==x)
return t->c;
t=t->next;
}
return 0;
}
node *get(){
return res;
}
void free_node(node *x){
return;
}```
```

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element