CountingSeries.cpp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <climits>
#include <cstring>
using namespace std;

typedef long long  int64;
typedef vector<int> vi;
typedef string ST;
typedef stringstream SS;
typedef vector< vector <int> > vvi;
typedef pair<int,int> ii;
typedef vector <string> vs;

#define Pf	printf
#define	Sf	scanf

#define	ep	1e-9
#define PI M_PI
#define E M_E

#define	CL(a, b)	memset(a, b, sizeof(a))
#define	mp	make_pair

#define	pb	push_back

#define	all(c)	(c).begin(), (c).end()
#define	tr(i, c)	for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

#define	present(x, c)	((c).find(x) != (c).end())		//map & set//
#define	cpresent(x, c)	(find(all(c),x) != (c).end())	//vector & list//

#define forn(i, n)	for(int i = 0, loop_ends_here = (int)n; i < loop_ends_here; i++)
#define forab(i, a, b)	for(int i = a, loop_ends_here = (int) b; i <= loop_ends_here; i++)
#define rep(i, a, b)	for(int i = a, loop_ends_here = (int)b; i>=loop_ends_here; i--)

class CountingSeries
{
public:
	long long countThem(long long a, long long b, long long c, long long d, long long upper)
	{
		vector <int64> gp;	gp.clear();
		if(d == 1LL) {
			if(c*d <= upper)
				gp.pb(c*d);
		}
		else {
			for(int64 t = c; t<= upper; t*=d)
				gp.pb(t);
		}

		vector <int64> agp;	agp.clear();
		tr(it, gp) {
			int64 t = *it;
			if( (t-a)%b == 0LL && (t-a)/b >= 0) agp.pb(t);
		}

		int64 count;
		if(a > upper)	count = 0;
		else		count = (upper - a)/b + 1;
		
		cout << "GP : ";
		tr(it, gp)	cout << *it << " ";
		cout << endl;

		cout << "AGP: ";
		tr(it, agp)	cout << *it << " ";
		cout << endl;
		
		cout << "AP : ";
		Pf("x = %lld, a+b*x = %lld\n", count-1, a+b*(count-1));



		return count + gp.size() - agp.size();
	}
};

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool KawigiEdit_RunTest(int testNum, long long p0, long long p1, long long p2, long long p3, long long p4, bool hasAnswer, long long p5) {
	cout << "Test " << testNum << ": [" << p0 << "," << p1 << "," << p2 << "," << p3 << "," << p4;
	cout << "]" << endl;
	CountingSeries *obj;
	long long answer;
	obj = new CountingSeries();
	clock_t startTime = clock();
	answer = obj->countThem(p0, p1, p2, p3, p4);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p5 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == p5;
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	all_right = true;
	
	long long p0;
	long long p1;
	long long p2;
	long long p3;
	long long p4;
	long long p5;
	
	{
	// ----- test 0 -----
	p0 = 1ll;
	p1 = 1ll;
	p2 = 1ll;
	p3 = 2ll;
	p4 = 1000ll;
	p5 = 1000ll;
	all_right = KawigiEdit_RunTest(0, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	{
	// ----- test 1 -----
	p0 = 3ll;
	p1 = 3ll;
	p2 = 1ll;
	p3 = 2ll;
	p4 = 1000ll;
	p5 = 343ll;
	all_right = KawigiEdit_RunTest(1, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	{
	// ----- test 2 -----
	p0 = 40ll;
	p1 = 77ll;
	p2 = 40ll;
	p3 = 100000ll;
	p4 = 40ll;
	p5 = 1ll;
	all_right = KawigiEdit_RunTest(2, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	{
	// ----- test 3 -----
	p0 = 452ll;
	p1 = 24ll;
	p2 = 4ll;
	p3 = 5ll;
	p4 = 600ll;
	p5 = 10ll;
	all_right = KawigiEdit_RunTest(3, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	{
	// ----- test 4 -----
	p0 = 234ll;
	p1 = 24ll;
	p2 = 377ll;
	p3 = 1ll;
	p4 = 10000ll;
	p5 = 408ll;
	all_right = KawigiEdit_RunTest(4, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	{
	// ----- test 5 -----
	p0 = 1000000000000ll;
	p1 = 1000000000000ll;
	p2 = 1000000000000ll;
	p3 = 100000ll;
	p4 = 1000000000000ll;
	p5 = 1ll;
	all_right = KawigiEdit_RunTest(5, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	{
	// ----- test 6 -----
	p0 = 371658585308ll;
	p1 = 274808924218ll;
	p2 = 611329026706ll;
	p3 = 75085ll;
	p4 = 848787675931ll;
	p5 = 3ll;
	all_right = KawigiEdit_RunTest(6, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	{
	// ----- test 7 -----
	p0 = 17340ll;
	p1 = 40451ll;
	p2 = 7763ll;
	p3 = 1ll;
	p4 = 3462ll;
	p5 = 0ll;
	all_right = KawigiEdit_RunTest(7, p0, p1, p2, p3, p4, true, p5) && all_right;
	// ------------------
	}
	
	if (all_right) {
		cout << "You're a stud (at least on the example cases)!" << endl;
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// You are given long longs a, b, c and d. The numbers a and b define an arithmetic progression that consists of all numbers of the form a + b*x, where x is a nonnegative integer. Likewise, c and d define a geometric progression that consists of all the numbers that are equal to c * d^y, where y is a nonnegative integer. You are also given a long long upperBound. Return the total number of integers between 1 and upperBound, inclusive, that belong to the arithmetic progression, the geometric progression or both.
// 
// DEFINITION
// Class:CountingSeries
// Method:countThem
// Parameters:long long, long long, long long, long long, long long
// Returns:long long
// Method signature:long long countThem(long long a, long long b, long long c, long long d, long long upperBound)
// 
// 
// NOTES
// -The ^ operator in this statement denotes the exponentiation operation. For example, 3^0 = 1 and 2^4 = 2*2*2*2 = 16.
// 
// 
// CONSTRAINTS
// -a, b, c and upperBound will each be between 1 and 1000000000000 (10^12), inclusive.
// -d will be between 1 and 100000 (10^5), inclusive.
// 
// 
// EXAMPLES
// 
// 0)
// 1
// 1
// 1
// 2
// 1000
// 
// Returns: 1000
// 
// The arithmetic progression is: 1, 2, 3, 4, ... .
// The geometric progression is: 1, 2, 4, 8, 16, ... . 
// Each positive integer is contained in at least one of the progressions.
// 
// 1)
// 3
// 3
// 1
// 2
// 1000
// 
// Returns: 343
// 
// This time, the arithmetic progression is: 3, 6, 9, 12, ... .
// The geometric progression is still: 1, 2, 4, 8, 16, ....
// There are 333 multiples of 3 between 1 and 1000, inclusive, and there are 10 powers of 2, 512 being the highest. As these two progressions do not have any common elements, the total result is 343.
// 
// 2)
// 40
// 77
// 40
// 100000
// 40
// 
// Returns: 1
// 
// 
// 
// 3)
// 452
// 24
// 4
// 5
// 600
// 
// Returns: 10
// 
// The 10 numbers are: 4, 20, 100, 452, 476, 500, 524, 548, 572 and 596.
// 
// 4)
// 234
// 24
// 377
// 1
// 10000
// 
// Returns: 408
// 
// 
// 
// END KAWIGIEDIT TESTING




//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!