One Day Trip: Nohashpolli, Safari Park

Date: 15:07:2017

Route details: 

  1. Dhanmondi 4 – Gazipur Chourasta (by VIP 27 bus). Cost: 70 per person

  2. Gazipur Chourasta-Nohashpolli (by leguna (local name)) cost: 600tk 6 person

  3. Entry tickets to Nohshpolli. cost: 1000tk 6 persons (normaly 200tk per person)

  4. Nohashpolli – Safari park ( by motor rikshaw (local name: kachim motor)). cost:  50 tk per person.

  5. Lunch. cost: depends on your preferences

  6. Safari park entry fees: 50 tk person

  7. Core Safari park bus ride: 100 tk per person

  8. Safari Park – Bagher Bazar(by auto). cost; 20tk person.

  9. Bagher bazar – Gazipyr Chourasta (by leguna). cost: 25 tk person.

  10. Gazipur chourasta – Dhanmondi 4 ( by VIP 27 bus). cost: 70 tk per person.


সুতপা’র ঠিকানা

“অনেক বেশি মনে পড়তেছে আমার আম্মাকে।”

UVA 11876 – N + NOD (N)



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.



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 to find divisors using primes.  Link is give below:

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




#define LL long long
#define L long

using namespace std;

L prime[1234567], mark[12345678],m;

void pr () {
    for (int i=4; i<12345678;i+=2)

    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) {

    for (int i=2;i<12345678;i++) {


bool checkprime( L a ) {

    L left = 0, right = m-1, mid;

    while ( left<=right ) { 

        mid = (left+right)/2; 

            return true; 
        else if (prime[mid]>a)
            right = mid-1;
            left = mid + 1;
    return false;


bool chcekcoprime(L a){

    L x = sqrt(a);

    if(checkprime(x) && x*x==a)
        return true;
       return false;

L num[1234567],di[1234567];

void divisors () {

    L c=2,d,e,f,g;

    for (L i=2;i<1234567;i++){
        d = sqrt(i)+1;

        else if (chcekcoprime(i))

            for (L j=0;prime[j]*prime[j]<=e;j++){ 





            if (e>1)


    return ;


void nu () {


    for (m=2;m<1234567;m++) { 






L lower (L a) {

    L left = 1, right = m, mid;

    while (left<=right) {

        mid = (left+right)/2;

        else if ( num[mid]>a)
            right = mid-1;
            left = mid + 1;


    return right;


L upper (L b) {

      L left = 1, right = m, mid;

    while (left<=right) {

        mid = (left+right)/2;

          left=mid+1; } 
        else if ( num[mid]>b)
            right = mid-1;
            left = mid + 1;

    return left;


int main() {
 //   freopen( "in.txt","r",stdin );

    pr ();

    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;