Solution of 11876 - N + NOD (N)

Problem Description
source:https://uva.onlinejudge.org/external/118/11876.uva

Consider an integer sequence N where, 

N0 = 1 
Ni = Ni−1 + NOD(Ni−1) for i > 0 
        Here, NOD(x) = number of divisors of x. 
        So the first few terms of this sequence are 1 2 4 7 9 12 18 ... 

Given two integers A and B, find out the number of integers in the above sequence that lies within the range [A, B]. 


Input 

The first line of input is an integer T (T < 100000), that indicates the number of test cases. Each case contains two integers, A followed by B (1 ≤ A ≤ B ≤ 1000000). 

Output 

For each case, output the case number first followed by the required result. 

Sample Input 

3 
1 18 
1 100 
3000 4000 

Sample Output 

Case 1: 7 
Case 2: 20 
Case 3: 87

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include<stdio.h>
#define max 1000000

using namespace std;
void generate();
void Nodgen();
long int dividor[max],Nodvalue[max],posi;

void generate()
{
    long int i, j, k;
    for(i=0;i<=max;i++)
        dividor[i]=1;
    for(i=2;i<=max;i++)
    {
        dividor[i]+=1;
        for(j=i+i;j<=max;j=j+i)
           dividor[j]+=1;
    }
}
void Nodgen()
{
    long int i,j;
    Nodvalue[0]=1;
    for(i=1;i<=max;i++)
    {
        Nodvalue[i]=Nodvalue[i-1]+dividor[Nodvalue[i-1]];
        if((Nodvalue[i-1]+dividor[i-1])>=1000000)
            break;
        posi=i;
    }
}
int main()
{
    long int t, a, b, i, j,count1,count2,s,temp,sum,value,low,mid,high,set;
    generate();
    Nodgen();
    while(scanf("%ld",&t)==1)
    {
        for(i=1;i<=t;i++)
        {
            scanf("%ld%ld",&a,&b);
            if(a!=1)
            {
                set=18;
                low=0;
                high=posi;
                while(set--)
                {
                    mid=(low+high)/2;
                    if(Nodvalue[mid]>a)
                        high=mid;
                    else
                        low=mid;
                }
                if(Nodvalue[high-1]==a)
                    count1=high-1;
                else
                    count1=high;
            }
            set=18;
            low=0;
            high=posi;
            while(set--)
            {
                mid=(low+high)/2;
                if(Nodvalue[mid]>b)
                    high=mid;
                else
                    low=mid;
            }
            count2=high;
            if(a==1)
                value=count2;
            else
                value=count2-count1;
            printf("Case %ld: %ld\n",i,value);
        }
    }
    return 0;
}