Codeforces 1133 problem D Zero Quantity Maximization —— 求a*k=b的最大数量

本文主要是介绍Codeforces 1133 problem D Zero Quantity Maximization —— 求a*k=b的最大数量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

You are given two arrays a and b, each contains n integers.

You want to create a new array c as follows: choose some real (i.e. not necessarily integer) number d, and then for every i∈[1,n] let ci:=d⋅ai+bi.

Your goal is to maximize the number of zeroes in array c. What is the largest possible answer, if you choose d optimally?

Input
The first line contains one integer n (1≤n≤2⋅105) — the number of elements in both arrays.

The second line contains n integers a1, a2, …, an (−109≤ai≤109).

The third line contains n integers b1, b2, …, bn (−109≤bi≤109).

Output
Print one integer — the maximum number of zeroes in array c, if you choose d optimally.

Examples
inputCopy
5
1 2 3 4 5
2 4 7 11 3
outputCopy
2
inputCopy
3
13 37 39
1 2 3
outputCopy
2
inputCopy
4
0 0 0 0
1 2 3 4
outputCopy
0
inputCopy
3
1 2 -1
-6 -12 6
outputCopy
3
Note
In the first example, we may choose d=−2.

In the second example, we may choose d=−113.

In the third example, we cannot obtain any zero in array c, no matter which d we choose.

In the fourth example, we may choose d=6.

题意：

给你一堆a和b，让你确定一个k，使得0=a*k+b的数量最大，问你最大数量是多少。

题解：

一开始是不想写这个水题的题解的，但是它让我wa了好几发，最终决定还是写一下。
首先就得到这个方程：k=bi/ai，注意ai=0的时候有两种情况
1.bi0，那么这个一定是0
2.bi！=0，那么就一定不是0，判掉这两种情况。
还有就是ai!=0,bi0的情况，那么这时候k=0，这也是一种要特殊处理的情况。
一开始我以为是逆元。。但是有负数，wa+1，然后用double，发现精度不够，wa+1，must位置写错，忘记改输入格式。。+1+1+1,。最后发现只需要用map存一下a和b除掉他们gcd对应的二元组即可，但是忘记考虑a是负数的情况，wa+1.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pa pair<int,int>
map<pa,int>mp;
const int N=2e5+5;
int a[N],b[N];
int main()
{int n,zero=0;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);int ans=0,must=0;for(int i=1;i<=n;i++){if(a[i]==0&&b[i]==0)must++;if(a[i]==0)continue;else if(b[i]==0)zero++;else{int g=__gcd((int)abs(a[i]),(int)abs(b[i]));if(a[i]<0)a[i]=-a[i],b[i]=-b[i];mp[{a[i]/g,b[i]/g}]++,ans=max(ans,mp[{a[i]/g,b[i]/g}]);//cout<<mp[{a[i]/g,b[i]/g}]<<endl;}}printf("%d\n",max(ans,zero)+must);return 0;
}

这篇关于Codeforces 1133 problem D Zero Quantity Maximization —— 求a*k=b的最大数量的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---