GeometricProgressions

SRM 500 · 2010-11-01 · by Chmel_Tolstiy

SRM 500 · 2010-11-01 · by Chmel_Tolstiy · Math, Simulation

Show categories

Class Name: GeometricProgressions

Return Type: int

Method Name: count

Arg Types: (int, int, int, int, int, int)

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*q1ⁱ, 0 <= i <= n1-1) and S2 = (b2*q2ⁱ, 0 <= i <= n2-1). Return the number of distinct integers that belong to at least one of these progressions.

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

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.

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.

1
1
1
0
0
1
Returns: 2

The progressions are (1) and (0).

3
4
100500
48
1024
1000
Returns: 100500

Each element of the second progression belongs to the first progression as well.

15724
19169
26501
6334
18467
42
Returns: 26543

153)

446185740
410498683
100500
268953270
164601714
100500
Returns: 201000

22 primes involved

Submissions are judged against all 228 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GeometricProgressions with a public method int count(int b1, int q1, int n1, int b2, int q2, int n2) · 228 test cases · 2 s / 256 MB per case