Efficient algorithm for converting number of days to years (including leap years)

The problem

I am writing a class for holding dates in c++, and I found the following problem:

I have a number of days N since a reference date (in my case that would be Jan 1, 0001 AD), including the leap days that passed since the reference day. How can I convert this number to a year Y, month M and day D efficiently?

I would like to do this as efficiently as possible, so the best implementation would obviously have O(1) complexity.

The next sections will explain some of the things I already learned.

Leap years

To determine if a year is leap or not, there are a few rules:

1. Years which are divisible by 4 are leap
2. Exception to rule 1: years that are divisible with 100 are not leap
3. Exception to rule 2: years that are divisible with 400 are leap

This would translate in code like this:

bool IsLeapYear(int year)
{
    // Corrected after Henrick's suggestion
    if (year % 400 == 0) return true;
    if ((year % 4 == 0) && (year % 100 != 0)) return true;
    return false;
}

An efficient method to calculate how many years are leap before an year would be:

int LeapDaysBefore(int year)
{
    // Years divisible by 4, not divisible by 100, but divisible by 400
    return ((year-1)/4 - (year-1)/100 + (year-1)/400);
}

Calculating the month

Once I find the year, I can calculate how many days there are until the current year, and I can subtract this number from N. This will give me the day of the year.

Keeping a table with the day number on which every month starts, we can easily calculate the month. I also created a function which will add 1 if the year is leap, and the month is greater or equal to 2.

// What day each month starts on (counting from 0)
int MonthDaySt[] = { 0, 31, 59, 90, 120, 151, 181, 212, 
    243, 273, 304, 334, 365 };

int MonthDayStart(int month, bool leap)
{
   if (leap && month >= 2) return MonthDaySt[month]+1;
   return MonthDaySt[month];
}

My idea

My algorithm is pretty complicated, and it looks like this:

void GetDate(int N, int &Y, int &M, int &D)
{
    int year_days;

    // Approximate the year, this will give an year greater or equal
    // to what year we are looking for.
    Y = N / 365 + 1;

    // Find the actual year, counting leap days
    do {
        Y--;

        // Calculate the actual number of days until the
        // approximate year
        year_days = Y * 365 + LeapDaysBefore(year);

    } while (year_days > N);

    // Add 1, because we start from year 1 AD (not 0)
    Y++;

    // Calculate month
    uint64_t diff = N - year_days; // Will give us the day of the year
    bool leap = IsLeapYear(Y);  // Is current year leap?

    // Use table to find month
    M = 0;
    while (MonthDayStart(M, leap) <= diff && M <= 12)
        M++;

    // Calculate day
    D = diff - MonthDayStart(M - 1, leap) + 1;
}

The function may have a few bugs (for example, it didn't work when N was 0).

Other notes

I hope that my algorithm is still correct, because I made some changes from the original for this question. If I missed something, or something was wrong, let me know to modify it. And sorry for the long question.