CF215A Bicycle Chain 题解

题意简述

给定一个长为 $n$ 的数列 $a$ 和一个长为 $m$ 的数列 $b$。

令 $f(i,j) = \dfrac{b_j}{a_i}$。令 $t=f(i,j)_ {max}$。问所有有序数对 $(i,j)$ 为 $t$ 的个数。

解题思路

注意到本题数据范围：$1 \leqslant n \leqslant 50 , 1 \leqslant m \leqslant 50$。

因为 $n \cdot m \leqslant 2500$，所以 $\Theta (nm)$ 完全能过这道题。选择枚举。

注意 $f(i,j) \in \mathbb{Z^+}$。所以要判读能否被整除。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],b[1000005];
int maxx,ans;
int main() {
	scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(b[j]%a[i]==0&&b[j]/a[i]>maxx) maxx=b[j]/a[i],ans=1;
			else if(b[j]%a[i]==0&&b[j]/a[i]==maxx) ans++;
		}
	}
	printf("%d",ans);
	return 0;
}
//code by TheCedar