首页 > itarticle > codeforces round #132(div2) a.bicycle chain

codeforces round #132(div2) a.bicycle chain

admin 12月 01, 2020 0

A. Bicycle Chain

time limit per test 2 seconds

time limit per test
1 second
memory limit per test
256 megabytes
input:standard input
output:standard output

Vasya’s bicycle chain drive consists of two parts: _n_ stars are attached to the pedal axle, _m_ stars are attached to the rear wheel axle. The chain helps to rotate the rear wheel by transmitting the pedal rotation.

We know that the _i_-th star on the pedal axle has _a__i_ (0 < _a_1 < _a_2 < … < _a__n_) teeth, and the _j_-th star on the rear wheel axle has _b__j_(0 < _b_1 < _b_2 < … < _b__m_) teeth. Any pair (_i_, _j_) (1 ≤ _i_ ≤ _n_; 1 ≤ _j_ ≤ _m_) is called a gear and sets the indexes of stars to which the chain is currently attached. Gear (_i_, _j_) has a gear ratio, equal to the value .

Since Vasya likes integers, he wants to find such gears (_i_, _j_), that their ratios are integers. On the other hand, Vasya likes fast driving, so among all “integer” gears (_i_, _j_) he wants to choose a gear with the maximum ratio. Help him to find the number of such gears.

In the problem, fraction denotes division in real numbers, that is, no rounding is performed.

Input

The first input line contains integer _n_ (1 ≤ _n_ ≤ 50) — the number of stars on the bicycle’s pedal axle. The second line contains _n_ integers _a_1, _a_2, …, _a__n_ (1 ≤ _a__i_ ≤ 104) in the order of strict increasing.

The third input line contains integer _m_ (1 ≤ _m_ ≤ 50) — the number of stars on the rear wheel axle. The fourth line contains _m_ integers _b_1, _b_2, …, _b__m_ (1 ≤ _b__i_ ≤ 104) in the order of strict increasing.

It is guaranteed that there exists at least one gear (_i_, _j_), that its gear ratio is an integer. The numbers on the lines are separated by spaces.

Output

Print the number of “integer” gears with the maximum ratio among all “integer” gears.

Examples

input

2
4 5
3
12 13 15

output

2

input

4
1 2 3 4
5
10 11 12 13 14

output

1

Note

In the first sample the maximum “integer” gear ratio equals 3. There are two gears that have such gear ratio. For one of them _a_1 = 4, _b_1 = 12, and for the other _a_2 = 5, _b_3 = 15.

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <utility>
#define ll long long
#define ull_ unsigned long long

using namespace std ;

int (){
    int a , b ;
    cin >> a ;
    int num_a[a + 10] ;
    for ( int i = 0 ; i < a ; i ++ ){
        cin >> num_a[i] ;
    }
    cin >> b ;
    int num_b[b + 10] ;
    for ( int i = 0 ; i < b ; i ++ ){
        cin >> num_b[i] ;
    }
    int ans = 0 ;
    int maxx = -1 ;
    for ( int i = 0 ; i < a ; i ++ ){
        for ( int j = 0 ; j < b ; j ++ ){
            if ( num_b[j] % num_a[i] == 0 ){
                maxx = max(maxx , num_b[j] / num_a[i]) ;
            }
        }
    }
    for ( int i = 0 ; i < a ; i ++ ){
        for ( int j = 0 ; j < b ; j ++ ){
            if ( num_b[j] % num_a[i] == 0 && num_b[j] / num_a[i] == maxx ){
                ans ++ ;
            }
        }
    }
    cout << ans << endl ;
    return 0 ;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能