GoodNumbers | Topcoder Archive

Problem Statement

You are given int[]s a, b and an int N. A positive integer x is called good if it satisfies "x is a multiple of a[i] but not a multiple of b[i]" for at least one i. Return the count of all good numbers between 1 and N, inclusive.

Definition

Class:: GoodNumbers
Method:: count
Parameters:: int[], int[], int
Returns:: int
Method signature:: int count(int[] a, int[] b, int N)
(be sure your method is public)

Constraints

N will be between 1 and 1,000,000,000, inclusive.
a will contain between 1 and 10 elements, inclusive.
a and b will contain the same number of elements.
Each element of a and b will be between 1 and N, inclusive.

Examples

```
{4}
```
```
{3}
```
```
20
```
```
Returns: 4
```
4, 8, 12, 16 and 20 are multiples of 4, but 12 is a multiple of 3. Thus 4, 8, 16 and 20 are good numbers.
```
{3,2}
```
```
{2,3}
```
```
9
```
```
Returns: 5
```
3 and 9 satisfy the condition for i=0. 2, 4 and 8 satisfy the condition for i=1. 2, 3, 4, 8 and 9 are good numbers.
```
{5,15,5,15}
```
```
{4,4,2,2}
```
```
50
```
```
Returns: 8
```
```
{1}
```
```
{1}
```
```
1000
```
```
Returns: 0
```
No number satisfies the condition.

{168120222,756,408,194,681,856,964,677,250,845}

{809,652,204,532,420,10,640688057,55,174076738,318}

1000000000

Returns: 16328141

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.