# CF215A Bicycle Chain

$ \texttt{Description} $

有多少对 $ (i,j) $ ,满足 $ b[j] \bmod a[i]==0 $ 并且 $ b[j]/a[i] $ 最大。

$ \texttt{Solution} $

这道题 $ n $ 和 $ m $ 很小,但我不用,我就要用 $ a_i $ 和 $ b_i $ 很小。

考虑枚举 $ a_i $ 是多少,然后枚举他的倍数,看是否有相应的 $ b_i $ ,这样就可以求出最大的倍数。

之后再枚举 $ a_i $ ,就可以知道相应的 $ b_i $ 应该是多少,再用乘法原理就好了。

$ \texttt{Code} $

n=read();
	for (i=1;i<=n;i++) x=read(),exist[x]++;
	m=read();
	for (i=1;i<=m;i++) x=read(),fre[x]++;
	//b[j]/a[i]
	for (i=1;i<=10000;i++)
	    if (exist[i])
	    for (j=1;j<=10000/i;j++)
	         if (fre[i*j])
	             ans=max(ans,j);
	for (i=1;i<=10000/ans;i++)
	    if (exist[i])
	        sum+=fre[i*ans]*exist[i];
	printf("%d\n",sum);

# CF215A Bicycle Chain

上一篇:给大家推荐一个免费的云平台-阿贝云


下一篇:文件管理基础命令之二