IntegralPerfectSquare

long long perfectSquare(long long num)
{
    // obvious cases
    int lastDigit = num % 10;
    if (num <= 0 || lastDigit == 2 || lastDigit == 3 || lastDigit == 7 || lastDigit == 8)
    {
        return 0;
    }

    long long section = 1;
    long long pow100 = 1;
    while (num / pow100 >= 100)
    {
        section++;
        pow100 *= 100;
    }

    long long period = num / pow100;  // first period
    long long remainder = num % pow100;
    long long quotient = 0;

    while (section > 0)
    {
        section--;
        pow100 /= 100;

        long long divisor;
        int newQuotientDigit;
        long long multi;
        for (newQuotientDigit = 9, divisor = quotient * 20 + newQuotientDigit; newQuotientDigit >= 0; newQuotientDigit--, divisor--)
        {
            multi = divisor * newQuotientDigit;
            if (period >= multi)
            {
                break;
            }
        }
        if (newQuotientDigit < 0)
        {
            return 0;
        }

        long long period_remain = period - multi;
        quotient = quotient * 10 + newQuotientDigit;

        if (section > 0)
        {
            period = period_remain * 100 + remainder / pow100;
            remainder = remainder % pow100;
        }
        else if (section == 0 && period_remain == 0 && remainder == 0)
        {
            return quotient;
        }
    }

    return 0;
}