UVa online judge 11876 N+NOD(N)

 UVA online judge

problem:11876

N+ NOD (N)

problem link(PDF):

https://uva.onlinejudge.org/external/118/11876.pdf

 

 SOLUTION:

#include<bits/stdc++.h>
using namespace std;
bool prime[1000009];
vector<int>num;
vector<int>pr;
int binary(int a)
{
    int mid,L=0,u=num.size()-1;
    while(L<=u)
    {
        mid=(u+L)/2;
        if(a>num[mid])
            L=mid+1;
        else if(a<num[mid])
            u=mid-1;
        else return mid;
    }
   return mid;
}

void sieve()
{ //sieve of Eratosthenes
    pr.push_back(2);
    prime[0]=prime[1]=1;  //1 means not prime
    for(int i=3; i<1000; i+=2)
        if(prime[i]==0)  //0 means prime
        {
            pr.push_back(i);
            for(int j=i*i; j<1000001; j+=i)
                prime[j]=1;
        }
    for(int i=1001; i<1000000; i+=2)
        if(prime[i]==0)
            pr.push_back(i);
}
int NOD(int z)
{
    if(prime[z]==0&&(z==2||z%2==1))

//even numbers aren't prime(without 2)
        return z+2;
    int y,n=z,nod=1;
    for(int a=0; pr[a]<=n; a++)
        if(n%pr[a]==0)
        {
            y=1;
            while(n%pr[a]==0)
            {
                y++;
                n/=pr[a];
            }
            nod*=y;
        }
    return nod+z;
}
void number()
{
    sieve();
    int m=0;
    num.push_back(1);
    while(num[m]<1000001)
    {
        m++;
        num.push_back(NOD(num[m-1]));
    }
    return;
}
int main()
{
    number();
    int T,A,B,b,c;
    scanf("%d",&T);
    for(int x=1; x<=T; x++)
    {
        scanf("%d%d",&A,&B);
        b=binary(A);
        if(num[b]<A) b++;
        c=binary(B);
        if(num[c]>B) c--;
        printf("Case %d: %d\n",x,c-b+1);
    }
    return 0;
}

 

 
 //Language:C++;

/* I used vector instead of array . I also used void . If you don't know about these things  stay with us to  know about it.*/

/* At first I made the N+NOD(N) series.To do so I used "Number Of Divisors" Algorithm which counts divisors of a number by prime factorization .I also used sieve of Eratosthenes to verify the prime numbers between 1&10^6. If you don't know these Algorithms  you will get TLE to solve the problem using the normal system of counting divisors. */

/* After taking input I counted the numbers of elements in the series between A&B by binary search.If you don't know about it you will get TLE to search A&B in general way. Because there may be 10^6 numbers in the range A&B. So stay with us to know about it.*/