## Description:

For a number N, first have to calculate N-1+divisors(N-1) & store it in array (e.g. arr[i]=arr[i-1]+divisors(arr[i-1])).

Make a sequence from 1 to until arr[i] becomes greater than 1000000. Then you will be given two numbers A & B, and you will have to find the number of integers from the above sequence which lies within the range [A,B].

Hints = No critical case. Easy problem.

## Algorithm:

**Step 1:**

First find the prime numbers from 1 to 1000000 and store them in an array (was not sure about the range, thats why I calculated till 1000000) .

**Step 2:**

Calculate number of divisors for each numbers from 1 to 1000000 and store divisors in each array. (e.g. divisors of 6 are 1,2,3,6. Total 4 divisors. So divisor[6]=4. )

* Step 3:* To find the divisors of each number, I took help of prime numbers. There is a good tutorial in lightoj.com to find divisors using primes. Link is give below:

http://lightoj.com/article_show.php?article=1003

To decrease time complexity,

I used here some tricks. First one is, when finding the number of divisors of a value, I checked if it is a prime or not. If the number is a prime then the divisors of that number is 2. Because prime numbers are divisible by 1 and the number it self only.

If the given number is not prime then I again checked if it is a co-prime. Because we know divisors of co-prime is 3 and they are 1, square root of that number(must be integer value, no fraction) and the number it self. So divisors of co-prime is 3.

If the number doesn’t meet the requirement of being prime, co-prime then I followed the algorithm I mentioned at the beginning of this step.

Number of divisors for 1 t0 5. divisor[1]=1, divisor[2]=2, divisor[3]=2, divisor[4]=3, divisor[5]=2, divisor[6]=4.

* Step 4:* So, I know the number of divisors of values from 1 to 1000000. Now I will calculate the sequence as described in problem description and will store it in a new array (e.g. num[2]=1+divisor[1], so, num[2] = 2, and num[3]=2+divisor[2], so, num[3] = 4).

* Step 5:* I will take the input as description. For given A & B, I will do binary search here to find lower bound of A and upper bound of B from num array. (the array which I used to store the sequence of numbers from 1 to 1000000) as problem description.

*Now I will subtract lower bound from upper bound and will save it in a new variable and again I will subtract 1 from this variable and will print this according to instruction. Why I did subtract 1? To understand this I think you need to know how lower bound and upper bound of binary search works!*

**Step 6:**I am enclosing the code here. Try not to see my code and try your own. Thanks

#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #define LL long long #define L long using namespace std; L prime[1234567], mark[12345678],m; void pr () { m=0; for (int i=4; i<12345678;i+=2) mark[i]=1; int N=sqrt(12345678)+1; for (int i=3;i<N;i+=2) { if (!mark[i]) { for (int j=i*i;j<12345678;j=j+i*2) { mark[j]=1; } } } for (int i=2;i<12345678;i++) { if(!mark[i]) prime[m++]=i; } } bool checkprime( L a ) { L left = 0, right = m-1, mid; while ( left<=right ) { mid = (left+right)/2; if(prime[mid]==a) return true; else if (prime[mid]>a) right = mid-1; else left = mid + 1; } return false; } bool chcekcoprime(L a){ L x = sqrt(a); if(checkprime(x) && x*x==a) return true; else return false; } L num[1234567],di[1234567]; void divisors () { L c=2,d,e,f,g; di[1]=1; for (L i=2;i<1234567;i++){ d = sqrt(i)+1; c=1; e=i; f=1; if(checkprime(i)) c=2; else if (chcekcoprime(i)) c=3; else{ for (L j=0;prime[j]*prime[j]<=e;j++){ f=0; while(e%prime[j]==0){ f++; e=e/prime[j]; } c*=(f+1); } if (e>1) c*=2; } di[i]=c; } return ; } void nu () { num[1]=1; for (m=2;m<1234567;m++) { num[m]=num[m-1]+di[num[m-1]]; if(num[m]>1234567) break; } return; } L lower (L a) { L left = 1, right = m, mid; while (left<=right) { mid = (left+right)/2; if(num[mid]==a){ right=mid-1; } else if ( num[mid]>a) right = mid-1; else left = mid + 1; } return right; } L upper (L b) { L left = 1, right = m, mid; while (left<=right) { mid = (left+right)/2; if(num[mid]==b){ left=mid+1; } else if ( num[mid]>b) right = mid-1; else left = mid + 1; } return left; } int main() { // freopen( "in.txt","r",stdin ); pr (); divisors(); nu(); int n; L A,B; scanf ("%d",&n); for (int i=1;i<=n;i++) { scanf ("%ld %ld",&A,&B); L lo=lower(A), up = upper (B); printf ("Case %d: %ld\n",i,up-lo-1); } return 0; }