HABLU-Hablu and Bablu

Hablu and Bablu

Below given c++ code is for hablu spoj or Hablu and Bablu spoj

Here in the question given a number "N" and "K" PRIMES or "1" now we have to find the total number of divisor of "N" which are not divisible by any given PRIME .

If one is present in array then it will divide any number so here our final answer will became "0"

1- > Now if one is not present and then rest will be all prime.So we start diving number "N" by given primes till the number is not divisible by that prime this process removes all prime "P" present in the number .

After above process we will do the prime factorization of  "N"(remains after first process) 

If the prime factorization is as follow :->

N = p1^a  * p2^b * p3^c * .......*pn^k;

then total number of divisor will be

total = (a+1)*(b+1)*(c+1) .......*(k+1);

So here our total answer will be total number of divisor of "N"(remains after first process).

If you still have problem you can mail me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
#define LL long long
bool a[1000009];
LL prime[80000];
int total;
void pre()
{
    for(int i=2;i<=1000;i++)
    {
        if(!a[i])
            for(int j=i*i;j<=1000000;j+=i)
                a[j]=true;
    }
    total=0;
    prime[total++]=2;
    for(int i=3;i<=1000000;i+=2)
        if(!a[i])
            prime[total++]=i;
}
int main()
{
    int t;
    pre();
    scanf("%d",&t);
    while(t--)
    {
        long long n,res=1,temp,in,count;
        int k;
        bool flag=false,flag2=false;
        scanf("%lld%d",&n,&k);
        temp=n;
        while(k--)
        {
            scanf("%lld",&in);
            if(in==1)
            {
                flag=true;
                continue;
            }
            while(temp%in == 0)
                temp/=in;
        }
        
        if(flag)
        {
            printf("0\n");
            continue;
        }
        if(temp==n)
            flag2=true;
        int l=0;
        while(prime[l]*prime[l]<=temp && l<total)
        {
            count=0;
            while(temp % prime[l] == 0)
            {
                count++;
                temp/=prime[l];
            }
            res*=count+1;
            l++;
        }
        if(temp>1)
            res*=2;
        if(flag2)
            res--;
        printf("%lld\n",res);
    }
}

IITKWPCF-Help Feluda with mathematical equations

Help Feluda with mathematical equations

Given below c++ code for iitkwpcf spoj or Help Feluda with mathematical equations spoj .
Here is the explanation of logic.
Given X²  + Y² + n = (X + Y)²
Now expanding it   
X²  + Y² + n = X²  + Y² + 2XY    ≡   n = 2XY   ≡  X = (n/2)*(1/y)
So we have to find only non-prime integral factor of “n/2” .and if “n” is odd then no integral “X” is possible so we will write 0 for all odd “n”.
Here my solution got accepted in 2.45 sec .Please help me to reduce the time complexity @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
#define LL long long
bool check(LL n)
{
    if(n==1)
        return true;
    for(LL i=2;i*i<=(n);i++)
        if(n%i==0)
            return true;
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL n,temp;
        scanf("%lld",&n);
        if(n==0)
        {
            printf("0 0\n");
            continue;
        }
        if(n&1)
        {
            printf("0\n");
            continue;
        }
        n>>=1;
        map<LL,int>mp;
        map<LL,int>::iterator t;
        for(LL i=1;i*i<=n;i++)
        {
            if(n%i==0)
            {
                if(check(i)){
                    mp[i]=1;
                }
                if(check(n/i))
                    mp[n/i]=1;
            }
        }
        printf("%d ",mp.size());
        for(t=mp.begin();t!=mp.end();t++)
            printf("%lld ",t->first);
        printf("\n");
    }
    return 0;
}

FRND-FRIENDSHIP!!!

FRIENDSHIP!!!

Below given c++ code for frnd spoj or friendship spoj.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,temp,t;
    long long bit[30]={0};
    cin>>n;
    t=n;
    if(n==1)
    {
        cin>>temp;
        cout<<temp;
        return 0;
    }
    while(t--){
        cin>>temp;
        for(int i=0;i<20;i++)
        {
            if((temp>>i) & 1)
                bit[i]++;
        }
    }
    long long res=0;
    for(int i=0;i<20;i++){
        res+=bit[i] * (n-bit[i])* (1<<i);
    }
    cout<<res;
    return 0;
}

NBIN-New Binary

New Binary

Below given code is for nbin spoj or new binary spoj.

Here in the first we have to formulate the sequence as we can know how many bits can accommodate given “n”;
Now let formulate the table:-

Number of Bits	Binary number at given Nth position	Given N
1	1	1
2	10	2
3	100	3
3	101	4
4	1000	5
4	1001	6
4	1010	7
5	10000	8
5	10001	9
5	10010	10
5	10100	11
5	10101	12

From the above table we can see that five digit binary number can accommodate at most 5 values .
Now by carefully seeing this we can see that if remove the two Most significant Bit from five digit binary number we can see that rest binary number are the number less than three digit binary as see below

10	000
10	001
10	010
10	100
10	101

As we cliff the Left part of table .By the rest we can formulate the DP as:
Position of the array represent the number of Bits and content of array represent the maximum “N” that or less can be represented using that or less number of Bit :

PRE_COMPUTE[i] = PRE_COMPUTE[i-1] + PRE_COMPUTE[i-2] + 1;

Now for getting result take the string of MAX = 72(because (N = 10¹⁵  ) Nth number can be accommodated in at max 72 Bit you will get that after calculating) initially containing all ZEROES now for the given “N” find the minimum POSITION in array  which can accommodate Nth number and after that make
N = N - PRE_COMPUTE[POSITION -1] - 1 .And repeat till N>0;(you will get this if you use pen and paper and write few steps)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define LEN 72
LL pre_com[100];
void pre()
{
    pre_com[1] = 1;
    pre_com[2] = 2;
    pre_com[3] = 4;
    pre_com[4] = 7;
    int i=4;
    while(pre_com[i] <=1000000000000000LL)
    {
        i++;
        p[i] = p[i-2]+1;
        pre_com[i] =pre_com[i-1] + pre_com[i-2]+1;
    }
}
int find(LL n)
{
    int low=0,high=LEN,mid;
    mid = (low + high)>>1;
    while(true)
    {
        mid = (low + high)>>1;
        if(pre_com[mid] < n)
        {
            if(pre_com[mid + 1] >n)
                return mid;
            else
                low = mid;
        }
        else
        {
            if(pre_com[mid - 1] < n)
                return mid - 1;
            else
                high = mid;
        }
    }
}
void print(LL n)
{
    bool a[80]={false};
    int pos  = find(n);
    int max = pos + 1;
    a[pos+1]=true;
    LL diff = n - pre_com[pos] - 1;
    while(diff>0)
    {
        pos = find(diff);
        a[pos+1] = true;
        diff = diff - pre_com[pos] - 1;
    }
    for(int i=max ;i>=1;i--)
        if(a[i])
            printf("1");
        else
            printf("0");
}
int main()
{
    pre();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL n;
        scanf("%lld",&n);
        print(n);
        printf("\n");
    }
    return 0;
}

NBIN-New Binary

New Binary

Below given code is for nbin spoj or new binary spoj.

Here in the first we have to formulate the sequence as we can know how many bits can accommodate given “n”;
Now let formulate the table:-

Number of Bits	Binary number at given Nth position	Given N
1	1	1
2	10	2
3	100	3
3	101	4
4	1000	5
4	1001	6
4	1010	7
5	10000	8
5	10001	9
5	10010	10
5	10100	11
5	10101	12

From the above table we can see that five digit binary number can accommodate at most 5 values .
Now by carefully seeing this we can see that if remove the two Most significant Bit from five digit binary number we can see that rest binary number are the number less than three digit binary as see below

10	000
10	001
10	010
10	100
10	101

As we cliff the Left part of table .By the rest we can formulate the DP as:
Position of the array represent the number of Bits and content of array represent the maximum “N” that or less can be represented using that or less number of Bit :

PRE_COMPUTE[i] = PRE_COMPUTE[i-1] + PRE_COMPUTE[i-2] + 1;

Now for getting result take the string of MAX = 72(because (N = 10¹⁵  ) Nth number can be accommodated in at max 72 Bit you will get that after calculating) initially containing all ZEROES now for the given “N” find the minimum POSITION in array  which can accommodate Nth number and after that make
N = N - PRE_COMPUTE[POSITION -1] - 1 .And repeat till N>0;(you will get this if you use pen and paper and write few steps)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define LEN 72
LL pre_com[100];
void pre()
{
    pre_com[1] = 1;
    pre_com[2] = 2;
    pre_com[3] = 4;
    pre_com[4] = 7;
    int i=4;
    while(pre_com[i] <=1000000000000000LL)
    {
        i++;
        p[i] = p[i-2]+1;
        pre_com[i] =pre_com[i-1] + pre_com[i-2]+1;
    }
}
int find(LL n)
{
    int low=0,high=LEN,mid;
    mid = (low + high)>>1;
    while(true)
    {
        mid = (low + high)>>1;
        if(pre_com[mid] < n)
        {
            if(pre_com[mid + 1] >n)
                return mid;
            else
                low = mid;
        }
        else
        {
            if(pre_com[mid - 1] < n)
                return mid - 1;
            else
                high = mid;
        }
    }
}
void print(LL n)
{
    bool a[80]={false};
    int pos  = find(n);
    int max = pos + 1;
    a[pos+1]=true;
    LL diff = n - pre_com[pos] - 1;
    while(diff>0)
    {
        pos = find(diff);
        a[pos+1] = true;
        diff = diff - pre_com[pos] - 1;
    }
    for(int i=max ;i>=1;i--)
        if(a[i])
            printf("1");
        else
            printf("0");
}
int main()
{
    pre();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        LL n;
        scanf("%lld",&n);
        print(n);
        printf("\n");
    }
    return 0;
}

POTIONS-Potions Class

Potions Class

Below given python code for potions spoj or potions class spoj.
In question a function is given for range query and seeing the number of query(q<100000) every query should be done in constant time O(1).Now having a look on function and trying to simplify it.

Now “w” is constant so taking it outside of summation

Now subtracting and adding “x” to  “i”  sp,

Now rearranging the above we get  

Since “x” is constant so taking it out of summation and taking common with

Now owr answer will be :..

If you have any problem in understanding the above logic you can mail me @ raj.nishant360@gmail.com

Below is Python 2.7 implementation of above logic.

import sys
t=int(sys.stdin.readline())
while t:
    n,q=map(int,sys.stdin.readline().split())
    s=raw_input().split()
    cum=[]
    cum2=[]
    for i in range(0,n+1):
        cum.append(0)
        cum2.append(0)
    for i in range(1,n+1):
        cum[i]=cum[i-1] + int(s[i-1])
        cum2[i]=cum2[i-1]+i*(int(s[i-1]))
    for i in range(0,q):
        w,x,y,z=map(int,sys.stdin.readline().split())
        lower = y+x
        higher = z+x
        result=(cum2[higher]-cum2[lower-1] + (w-x)*(cum[higher]-cum[lower-1]))%1000000007
        sys.stdout.write(str(result))
        sys.stdout.write("\n")
    t=t-1

SUBXOR-SubXor

SubXor

Given below c code for subxor spoj

Here I am posting iterative and recursive method to implement Tries.But if you want to understand the problem then follow recursive method.

Here question is based on concept of xor and I have implemented it through Trie .

Basic idea is :-

xor(i,j) means XOR of elements from indexed i to j of an Array

XOR(i,j) = XOR(1,i-1)^XOR(1,j);

This can be proved as 

A^A = 0     & A^0 = A;

Hence if we XOR the total XOR from 1 to j with total XOR from 1 to i-1 ,it will nullify the effect  of XOR(1,i-1) in XOR(1,j) and the remaining XOR will be XOR(i,j);

If you want to study about Tries then CLICK HERE

If you still have problem you can ask me @ raj.nishant360@gmail.com

Iterative Method to implement add and query function

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int lCount,rCount;
    Node *lChild,*rChild;
    Node()
    {
        lCount=rCount=0;
        lChild=rChild=NULL;
    }
};
void addBit(Node *root,int n)
{
    for(int i=20;i>=0;i--)
    {
        int x= (n>>i) & 1;
    
        if(x)
        {
            root->rCount++;
            if(root->rChild == NULL)
                root->rChild = new Node();
            root = root->rChild;
        }
        else
        {
            root->lCount++;
            if(root->lChild == NULL)
                root->lChild = new Node();
            root = root->lChild;
        }
    }
}
int query(Node *root,int n,int k)
{
    if(root == NULL)
        return 0;
    int res = 0;
    for(int i=20;i>=0;i--)
    {
        bool ch1=(k>>i) & 1;
        bool ch2=(n>>i) & 1;
        if(ch1)
        {
            if(ch2){
                res+=root->rCount;
                if(root->lChild == NULL)
                    return res;
                root = root->lChild;
            }

            else{
                res+=root->lCount;
                if(root->rChild == NULL)
                    return res;
                root = root->rChild;
            }
        }
        else
        {
            if(ch2){
                if(root->rChild == NULL)
                    return res;
                root= root->rChild;
            }
            else{
                if(root->lChild == NULL)
                    return res;
                root= root->lChild;
            }
        }
    }
    return res;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        int temp,temp1,temp2=0;
        Node *root = new Node();
        addBit(root,0);
        long long total =0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&temp);
            temp1= temp2^temp;
            total+=(long long)query(root,temp1,k);
            addBit(root , temp1);
            temp2 = temp1;
        }
        printf("%lld\n",total);
    }
    return 0;
}

PAML-Popoye and the magical land

Popoye and the magical land 

given below c code for pamlspoj or Popoye and the magical land spoj.
question is simple but if you still feel problem then ask me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int t,k;
 scanf("%d",&t);
 for(k=1;k<=t;k++)
 {
  int n,temp;
  vector<int>v;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
   scanf("%d",&temp);
   v.push_back(temp);
  }
  int height=0,max_h=-1,count=-1;
  sort(v.begin(),v.end());
  bool status = true;
  while(status)
  {
   status = false;
   for(int i=0;i<n;i++){
    if(v[i]!=-1)
     status=true;
   }
   count++;
   for(int i=0;i<n;i++)
   {
    if(v[i]>=height)
    {
     height++;
     v[i]=-1;
    }
   }
   if(max_h<height)
    max_h=height;
   height = 0;
  }
  printf("Case #%d: %d %d\n",k,count,max_h);
 }
 return 0;
}

DCEPC11B-Boring Factorials

Boring Factorials

given below code for dcepc11b spoj or boring factorial spoj.

here the problem is based on two main concepts 

1 -> Wilson’s Theorem 

2 -> Inverse modulo (It can be found by Extended Euclidean Algorithm , Fermat’s Little Theorem ,Euler’s Theorem)

here in this problem i have used Fermat's theorem 

Wilson’s Theorem 

According to Wilson's Theorem     for all prime n;(for proof of Wilson's Theorem click on link)

Now from this we can write :

Here my solution get accepted in 1.83 sec can any body help me in optimizing this solution or any other solution which get accepted in lower time please mail me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL pow_mod(LL a,LL b,LL m)
{
 LL x=1,y=a;
 while(b>0)
 {
  if(b & 1)
   x=(x*y)%m;
  y=(y*y)%m;
  b>>=1;
 }
 return x;
}
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  LL n,p,i,result=-1,temp;
  scanf("%lld%lld",&n,&p);
  if(n>=p)
  {
   printf("0\n");
   continue;
  }
  for(i=n+1;i<p;i++)
  {
   temp=pow_mod(i,p-2,p);
   result=(result*temp)%p;
  }
  printf("%lld\n",p+result);
 }
 return 0;
}

aps-Amazing Prime Sequence

Amazing Prime Sequence

given below c code for aps spoj or amazing prime sequence.

If you have any quarry you can mail me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
int p[10000009];
long long res[10000009];
void pre()
{
 for(int i=2;i<=10000000;i++)
 {
  if(!p[i])
  {
   for(int j=i+i;j<=10000000;j+=i)
    if(!p[j])
     p[j]=i;
   res[i]=res[i-1]+i;
  }
  else
   res[i]=res[i-1]+p[i];
 }
}
int main()
{
 int t;
 pre();
 scanf("%d",&t);
 while(t--)
 {
  int n;
  scanf("%d",&n);
  printf("%lld\n",res[n]);
 }
 return 0;
}

WPC5I-LCM

LCM

given below c code for wpc5i spoj or lcm spoj.

If you have any problem you can ask me @ raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n,m;
  scanf("%d%d",&n,&m);
  map<int ,int>mp1,mp2,result;
  map<int ,int>::iterator t;
  for(int i=2;i*i<=n;i++)
  {
       while(n%i==0)
       {
           mp1[i]+=1;
           n/=i;
        }
  }
  if(n>1)
     mp1[n]+=1;
  for(int i=2;i*i<=m;i++)
  {
        while(m%i==0)
        {
            mp2[i]+=1;
            m/=i;
        }
  }
  if(m>1)
     mp2[m]+=1;
  long long k=1;
  for(t=mp1.begin();t!=mp1.end();t++)
  {
       if(t->second > mp2[t->first])
           result[t->first]=t->second;
  } 
  for(t=mp2.begin();t!=mp2.end();t++)
  {
       if(t->second > mp1[t->first] && result[t->first] < t->second)
            result[t->first]=t->second;
  }
  for(t=result.begin();t!=result.end();t++)
       for(int i=0;i<t->second;i++)
            k*=(long long)(t->first);
  printf("%lld\n",k);
 }
 return 0;
}