夹缝

问题描述：

二维空间内有两面相对放置的，向无限远延伸的镜子，以镜子的方向及其法向量建立坐标系，我们选
定一个法向量方向下面称“上”。
在镜子上的整数位置，存在着一些传感器，传感器不影响光线的反射，光线仍旧满足反射定律（即入
射角等于出射角）。
你可以在两面镜子上各选定一个整数位置的点 A 与 B，并从其中一个点向另一个射出一条光线，我
们希望接收到光线的传感器数量尽可能的多。

 

考试打了暴力+随机骗分。然而还没有一些巨佬直接小范围暴力求答案取max来的分高...

首先是结论：①假设步长为k，那么步长为(2t+1)k的时候覆盖的点是没有直接K来的优秀的，简单易证,感性理解一下

　　　　　　②若起点为s，步长为k,那么一边的经过x的条件是：x=s+2tk,另一边经过y的条件是y=s+k+2tk(t∈Z)

所以只要求步长为$2^i$时就好了

 1 #pragma GCC optimize("Ofast")
 2 #include<bits/stdc++.h>
 3 #define qqq register
 4 using namespace std;
 5 inline int read(){
 6     int ans=0,f=1;char chr=getchar();
 7     while(!isdigit(chr)){if(chr=='-')f=-1;chr=getchar();}
 8     while(isdigit(chr)) {ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
 9     return ans*f;
10 }const int M=300005;
11 int n,m,h,res,p[M],q[M],c[M],ans;
12 inline void cmax(int &x,int y){if(x<y) x=y;}
13 int Calc(int x,int z){
14     x%=z;
15     if(x<0) x+=z;
16     return x;
17 }
18 int Calc(int x,int y,int z){
19     x%=z;
20     x+=y;
21     if(x<0) x+=z;
22     if(x>=z) x-=z;
23     return x;
24 }
25 int main(){
26     freopen("mirror.in","r",stdin);
27     freopen("mirror.out","w",stdout);
28     n=read(),m=read(),h=read();ans=2;
29     for(qqq int i=1;i<=n;++i) p[i]=read();
30     for(qqq int i=1;i<=m;++i) q[i]=read();
31     int ppp=log(1e9)/log(2);
32     for(qqq int i=0;i<=ppp;++i){
33         int t1=1<<i;
34         int t2=1<<i+1;
35         int tot=0;
36         for(qqq int j=1;j<=n;++j) c[++tot]=Calc(p[j],t2);
37         for(qqq int j=1;j<=m;++j) c[++tot]=Calc(q[j],t1,t2);
38         sort(c+1,c+tot+1);
39         for(qqq int j=1,k;j<=tot;){
40             for(k=j;k<=tot&&c[k]==c[j];++k);
41                 cmax(ans,k-j);j=k;
42         }
43     }cout<<ans;
44     return 0;
45 }