Topcoder SRM 523 Div1 250pt

523.cpp

// Topcoder SRM 523 Div1 250pt
// problem: http://community.topcoder.com/stat?c=problem_statement&pm=10957&rd=14548
// coded by jong10

#include <iostream>
using namespace std;
#define ARRAY_SIZE(a) (sizeof(a) / sizeof((a)[0]))

// cut here start -------------------------------------------------------------

#include <cmath>

class CountingSeries {
    long long max(long long a, long long b) {
        return a >= b ? a : b;
    }
public:
    long long countThem(long long a, long long b, long long c, long long d, long long upper) {
        long long count_same = 0, count_x = 0, count_y = 0;
        long long min_x, max_x, min_dy, max_dy;

        min_x = max(0, (long long)ceil((1 - a) / double(b)));
        max_x = (long long)floor((upper - a) / double(b));
        count_x = max_x - min_x + 1;
        //cout << min_x << " <=  x  <= " << max_x << "\n";

        min_dy = max(0, (long long)ceil(1.0 / double(c)));
        max_dy = (long long)floor(upper / double(c));
        //cout << min_dy << " <= d^y <= " << max_dy << "\n";

        for (long long dy = min_dy; dy <= max_dy; dy *= d) {
            //cout << "\tdy: " << dy << endl;
            count_y++;

            // find: c * d^y == a + b * x
            //       ((c * d^y) - a) / b == x
            long long x = (long long)((c * dy - a) / double(b));
            if (min_x <= x && x <= max_x && a + b * x == c * dy)
                count_same++;

            if (dy == 0 || d == 1)
                break;
        }

        //cout << "cnt(x)=" << count_x << ", ";
        //cout << "cnt(y)=" << count_y << ", ";
        //cout << "cnt(same)=" << count_same << "\n";
        //cout << "----------" << endl;

        return count_x + count_y - count_same;
    }
};

// cut here end ---------------------------------------------------------------

static long long D[][6] = {
    {1, 1, 1, 2, 1000, 1000},
    {3, 3, 1, 2, 1000, 343},
    {40, 77, 40, 100000, 40, 1},
    {452, 24, 4, 5, 600, 10},
    {234, 24, 377, 1, 10000, 408},
};

int main() {
    CountingSeries c;
    for (int i = 0; i < ARRAY_SIZE(D); i++) {
        cout << "#case " << i
                << ": a=" << D[i][0]
                << ", b=" << D[i][1]
                << ", c=" << D[i][2]
                << ", d=" << D[i][3]
                << ", upper=" << D[i][4] << endl;

        long long output = c.countThem(D[i][0], D[i][1], D[i][2], D[i][3], D[i][4]);

        cout << "(expect) " << D[i][5] << "\n"
                << "(output) " << output << "\n"
                << "(result) " << (D[i][5] == output ? "[SUCCESS]" : "") << "\n\n";
    }
    return 0;
}