Here you will find solutions of many problems on spoj. If you want solution of some problem which is not listed in blog or have doubt regarding any spoj problem (which i have solved) or any programming concept (data structure) you can mail me @ raj.nishant360@gmail.com
And my humble request to you all that don't copy the code only try to understand the logic and algorithm behind the code. I have started this because if you tried as hard as you can and still can't find any solution to the problem then you can refer to this.
You can read my answer how to start competitive programming CLICK HERE

Saturday, May 31, 2014

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);
    }
}