UVA 11876 - N + NOD (N)

#include<bits/stdc++.h>
using namespace std;
long divisor[1000010],ar[1000010]={0},tot;
void divisors()
{
    long i,j;
    for(i=1;i<=1000000;i++)
    {
        for(j=i;j<=1000000;j+=i)
            divisor[j]++;
    }
}
long binarysearch(long start,long ennd,long ele)
{
    while(start<ennd)
    {
        long mid=(start+ennd)/2;
        if(ele==ar[mid])
            return mid;
        else if(ele==ar[start])
            return start;
        else if(ele==ar[ennd])
            return ennd;
        else if(ele>ar[mid])
        {
            start=mid+1;
        }
        else if(ele<ar[mid])
        {
            ennd=mid-1;
        }
    }
    return start;
}
void nod()
{
    memset(ar,0,sizeof(ar));
    ar[0]=1;
    ar[1]=2;
    ar[2]=4;
    long i;
    for(i=3;ar[i-1]<1000010;i++)
    {
        ar[i]=ar[i-1]+divisor[ar[i-1]];
        tot=i;
    }
}
int main()
{
    divisors();
    nod();
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long fst,scnd,a,b;
        cin>>a>>b;
        fst=binarysearch(0,tot,a);
        scnd=binarysearch(0,tot,b);
        if(ar[fst]<a)
            fst++;
        if(ar[scnd]>b)
            scnd--;
        printf("Case %ld: %ld\n",cs++,scnd-fst+1);
    }
}