$$\Large\texttt{My Blog}$$


Description

题目链接:Codeforces 724C

有一个 $n\times m$ 的矩形,四周有围墙围起来,其左上角和右下角的坐标分别为 $(0,0)$ 和 $(n,m)$ 。从 $(0,0)$ 开始以 $\sqrt 2$ 个单位每秒的速度向 $(1,1)$ 的方向发射一束光线,每次遇到墙都正常反射(符合物理的反射),光线射到顶点会被吸收。在这个矩形内有 $k$ 个点,坐标分别为 $(x_i,y_i)$ ,求每个点第一次被光线经过的时刻。

数据范围: $2\le n,m\le 10^5$ , $1\le k\le 10^5$ , $1\le x_i<n$ , $1\le y_i<m$


Solution

对于这类矩形内上的反射问题,我们可以将矩形无限展开,那么相当于我们把点按照矩形边界对称,光线也就边成了一条直线

我们考虑对称后的点的坐标是什么。如果原来的坐标为 $(x,y)$ ,那么按照第 $k$ 条横轴展开的坐标为 $(x,2km-y)$ ,按照第 $k$ 条纵轴展开的左边为 $(kn-x,y)$ 。因此,如果我们沿着若干条轴展开后,坐标一定可以写成 $(k_1n\pm x,k_2m\pm y)$ 的形式。

由于我们知道了展开后的坐标,那么有如下方程: $$k_1n\pm x=k_2m\pm y\Longrightarrow k_1n-k_2m=\pm x\pm y$$ 发现这是一个丢番图方程,我们可以直接解出 $(k_1,k_2)$ 的通解。

但是,题目中规定光线在矩形顶点位置会被吸收,那么我们就要保证坐标的绝对值小于等于 $\operatorname{lcm}(n,m)$ ,否则光线一定会经过 $\operatorname{lcm}(n,m)$ 这个点而被吸收。

因此,我们对 $4$ 种情况分别求解,找到一组解使得 $k_1n\pm x$ 的值尽量小且大于 $0$ 。形象地说,就是使得 $k_1n\pm x$ 最小并满足 $0<k_1n\pm x<\operatorname{lcm}(n,m)$ 。

这个最小的符合条件的解就是答案。

时间复杂度: $O(k\log n)$


Code

#include <cstdio>
#include <algorithm>
typedef long long LL;

const LL INF=1LL<<60;
int n,m,k;
LL mx;

int gcd(int a,int b) {
    return b?gcd(b,a%b):a;
}
int exgcd(int a,int b,int &x,int &y) {
    if(!b) {x=1,y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x; return d;
}
LL solve(int dx,int dy) {
    int a=2*n,b=-2*m,c=dy-dx,x,y;
    int d=exgcd(a,b,x,y);
    if(c%d) return INF;
    a/=d,b/=d,c/=d,b=std::abs(b),x=(x*c%b+b)%b;
    LL ans=2LL*n*x+dx;
    if(ans<=0||ans>=mx) return INF;
    return ans;
}
int main() {
    scanf("%d%d%d",&n,&m,&k);
    mx=1LL*n*m/gcd(n,m);
    while(k--) {
        int x0,y0;
        scanf("%d%d",&x0,&y0);
        LL ans=INF;
        ans=std::min(ans,solve(+x0,+y0));
        ans=std::min(ans,solve(+x0,-y0));
        ans=std::min(ans,solve(-x0,+y0));
        ans=std::min(ans,solve(-x0,-y0));
        printf("%lld\n",ans==INF?-1:ans);
    }
    return 0;
}