【Codeforces Round #544 (Div. 3) D. Zero Quantity Maximization】GCD

D. Zero Quantity Maximization

题意

给你两个长度为$n$的数组$a$,$b$，$c_i=a_i\times d+b_i$,现在找到一个$d$使尽量多的$c_i$为$0$。
$1\le n\le 10^5$
$?10^9\le a_i,b_i\le 10^9$
做法

设$c_i=0$,那么$d=?\frac{b_i}{a_i}$，只需要看哪个d出现次数最多即可，这里我怕被卡精度，于是存分数约分后的最简形式即可，这里要注意$a_i=0,b_i=0$等情况。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 2e5+5;
map<pii,int> mp;
int a[maxn],b[maxn];
int main()
{
    int n;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;int tmp=0;for(int i=1;i<=n;i++){
    if(a[i]==0&&b[i]==0){
    tmp++;continue;}else if(a[i]==0) continue;if(b[i]==0){
    mp[pii(0,1)]++;ans=max(ans,mp[pii(0,1)]);continue;}int up=-b[i]/__gcd(a[i],b[i]);int down=a[i]/__gcd(a[i],b[i]);if(up<0){
    up=up*-1;down=down*-1;}mp[pii(up,down)]++;ans=max(ans,mp[pii(up,down)]);}printf("%d\n",ans+tmp);return 0;
}