UVA 11876 – N + NOD (N)

 

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.
Step 6: 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!

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;
}



Advertisements