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