Connection Status:
Competition Arena > CountingSeries

CountingSeries

SRM 523 · 2011-05-25 · by vexorian

SRM 523 · 2011-05-25 · by vexorian · Math
Class Name: CountingSeries
Return Type: long
Method Name: countThem
Arg Types: (long long, long long, long long, long long, long long)
Problem Statement

Problem Statement

You are given 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 upperBound. Return the total number of integers between 1 and upperBound, inclusive, that belong to the arithmetic progression, the geometric progression or both.

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)
1000000000000
1000000000000
1000000000000
100000
1000000000000
Returns: 1

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

Coding Area

Language: C++17 · define a public class CountingSeries with a public method long long countThem(long long a, long long b, long long c, long long d, long long upperBound) · 537 test cases · 2 s / 256 MB per case

Submitting as anonymous