Codeforces 1041F Ray in the tube

题面在这里

题意：一根管道，上下边界分别有一些传感器，射出一条光线在管内反弹，问最多射到多少个传感器上

​

首先考虑出射点\(x_a\)和第一个反弹点\(x_b\)的横坐标差\(d\)

那么在\(x_a\)所在直线上的\(x_a+d\cdot 2k\)位置会被射到

\(x_b\)所在直线上的\(x_a+d\cdot (2k+1)\)位置会被射到

发现都是\(d\)的奇数/偶数倍

那么显然\(d=2^l,(l\gt 0)\)

然后爆枚\(d\)，所有同余\(2d\)的位置都是同时被打到的

​

示例程序：

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;

const int maxn=100005;
int n,m,a[maxn],b[maxn],ty,ans;
map<int,int> numa,numb;
void calc(int l){
	numa.clear(); numb.clear();
	l++;int p=1; while (l--) p=p*2;
	for (int i=1;i<=n;i++) numa[a[i]%p]++;
	for (int i=1;i<=m;i++) numb[b[i]%p]++;
	for (int i=1;i<=n;i++)
	 ans=max(ans,numa[a[i]%p]+numb[(a[i]+p/2)%p]);
	for (int i=1;i<=m;i++)
	 ans=max(ans,numa[(a[i]+p/2)%p]+numb[a[i]%p]);
}
int main(){
	scanf("%d%d",&n,&ty);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d%d",&m,&ty);
	for (int i=1;i<=m;i++) scanf("%d",&b[i]);
	ans=2;
	for (int i=0;i<30;i++) calc(i);
	printf("%d",ans);
	return 0;
}