GoodNumbers

TCO13 Semifinal 2 · 2013-02-19 · by snuke

TCO13 Semifinal 2 · 2013-02-19 · by snuke · Math

Show categories

Class Name: GoodNumbers

Return Type: int

Method Name: count

Arg Types: (vector<int>, vector<int>, int)

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.

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

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

Coding Area

Language: C++17 · define a public class GoodNumbers with a public method int count(vector<int> a, vector<int> b, int N) · 88 test cases · 2 s / 256 MB per case