TopCoder problem "GeometricProgressions" used in SRM 500 (Division II Level Three)



Problem Statement

    NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.



You are given two geometric progressions S1 = (b1*q1i, 0 <= i <= n1-1) and S2 = (b2*q2i, 0 <= i <= n2-1). Return the number of distinct integers that belong to at least one of these progressions.
 

Definition

    
Class:GeometricProgressions
Method:count
Parameters:int, int, int, int, int, int
Returns:int
Method signature:int count(int b1, int q1, int n1, int b2, int q2, int n2)
(be sure your method is public)
    
 

Constraints

-b1 and b2 will each be between 0 and 500,000,000, inclusive.
-q1 and q2 will each be between 0 and 500,000,000, inclusive.
-n1 and n2 will each be between 1 and 100,500, inclusive.
 

Examples

0)
    
3
2
5
6
2
5
Returns: 6
The progressions in this case are (3, 6, 12, 24, 48) and (6, 12, 24, 48, 96). There are 6 integers that belong to at least one of them: 3, 6, 12, 24, 48 and 96.
1)
    
3
2
5
2
3
5
Returns: 9
This time the progressions are (3, 6, 12, 24, 48) and (2, 6, 18, 54, 162). Each of them contains 5 elements, but integer 6 belongs to both progressions, so the answer is 5 + 5 - 1 = 9.
2)
    
1
1
1
0
0
1
Returns: 2
The progressions are (1) and (0).
3)
    
3
4
100500
48
1024
1000
Returns: 100500
Each element of the second progression belongs to the first progression as well.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11343

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14429&pm=11343

Writer:

Chmel_Tolstiy

Testers:

PabloGilberto , ivan_metelsky , Smylic

Problem categories:

Math, Simulation