UVA 11876 N + NOD (N) Solution

 

Solution in C++:

///**********ALLAH IS ALMIGHTY************///

///AH Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh   

#include<bits/stdc++.h>

using namespace std;

const int mx=1000000;

 int d[mx+2];

int i,j,a,b,t;

int main()

{

    memset(d,0,sizeof d);

    for(i=1;i<=mx;i++)

    {

        for(j=i;j<=mx;j+=i)

        {

           ++d[j];

        }

    }

    vector<int>s(mx+1,0);

    s[0]=1;

    for(i=1;i<=mx;i++)

    {

        s[i]=s[i-1]+d[s[i-1]];

    }

    cin>>t;

    for(i=1;i<=t;i++)

    {

        cin>>a>>b;

         printf("Case %d: ",i);

         cout<<distance(lower_bound(s.begin(),s.end(),a),upper_bound(s.begin(),s.end(),b))<<endl;

    }

}