题解：CF2097C Bermuda Triangle

· · 题解

简述题意

分析

这个问题说球可以反弹，十分的难以计算。我们不妨考虑球匀速直线运动，但是球桌通过轴对称布满平面。我们惊人的发现去找球的运动轨迹与密铺三角形的顶点的交点的效果和原问题是等价的。

首先考虑判断无解。这一步我们将时间的秒数化为整数方便计算，那么我们只需要将 v_x 和 v_y 除以 \gcd(v_x,v_y) 就可以了。

然后我们假设进袋时间是 M，那么就有以下的两个同余方程：

x + Mv_x \equiv 0 \pmod n y + Mv_y \equiv 0 \pmod n

分别解这两个方程可以使用 exgcd。如果这两个方程的任何一个无解，那么这个问题就无解。

但是这两个方程解出来的 M 可能不一样，不妨假设分别解得特解 M_x 和 M_y，那么我们就需要看是否可能找到另外两个解让 M_x=M_y。

根据二元一次方程通解公式，我们可以得到：

M_x+k\times \frac{x}{\gcd(x,v_x)}=M_y+p\times \frac{y}{\gcd(y,v_y)}

其中 k,p 是整数。解这一个方程我们可以使用 exgcd 解出 k,p，这个方程无解那么这个问题就无解。然后我们在倒退就可以算出真正的 M。

好，有了 M 我们就能计算出球直线运动后的终点坐标 (t_x,t_y)。原问题中反弹了几次的问题就等价于现在的：“球运动的这个线段中与密铺的三角形的线段相交了几次？”

我们分 4 类考虑：竖直的、水平的、左下往右上斜的和左上往右下斜的。前两类只需要使用终点的对应坐标除以 n 再减一就可以了。（因为起点在最左下的三角形内，减一是为了减去终点碰到的那根线）而后两类就复杂一些，我们暂时不考虑减去终点碰到的那根线这回事。

左上往右下斜的线上的点的坐标满足 x+y 是一个定值，但是我们发现这个密铺三角形的图案里面不是所有 n 的倍数都可以作为 x+y 的定值使得左上往右下斜的线出现的。这个数必须是 n 的奇数倍数。这也不难，我们直接将终点的横纵坐标加起来再加一个 n，这个时候条件就变成了 n 的偶数倍数，所以线的个数就是 \lfloor \frac{t_x+t_y+n}{2n} \rfloor。

另一种斜向的线同理。需要注意的是，另一种斜向的线上的点满足差值是定值，如果直接套用上面的式子会错，得加一个绝对值。

最后的问题：处理终点的额外计算的线的个数。这里我想到了一种偷懒的办法，还是以左上往右下斜的线为例，如果终点位于这根线上，那么一定有：t_x+t_y+n=2qn，其中 q 是整数；否则就有：t_x+t_y+n=(2q+1)n，其中 q 是整数。我们要让第一种情况答案减一，第二种情况答案不变，我们发现，只要不加那个 n 就能达到我们的目的。另一种情况也是一样的。

然后就做完了，值得注意的是这种方式的中间步骤可能爆 long long，得用 int128。听着很复杂实际上写着比较简单。

代码

#include<bits/stdc++.h>
using namespace std;
#define int __int128
int gcd(int a,int b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a*b/gcd(a,b);
}
void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int x_=x,y_=y;
    x=y_;
    y=x_-(a/b)*y_;
}
int read(){}//快读快写省略，目的是配套int128
void write(int x){}
signed main(){
    int t=read();
    while(t--){
        int n=read(),x=read(),y=read(),vx=read(),vy=read();
        int g=gcd(vx,vy);
        vx/=g;
        vy/=g;
        if(x%gcd(vx,n)!=0||y%gcd(vy,n)!=0){
            cout<<-1<<"\n";
            continue;
        }
        int gx=gcd(vx,n),gy=gcd(vy,n);
        int mx,kx,my,ky;
        exgcd(vx/gx,n/gx,mx,kx);
        exgcd(vy/gy,n/gy,my,ky);
        mx*=x/gx;
        my*=y/gy;
        mx=-mx;
        my=-my;//注意正负性啊
        if(max(my-mx,mx-my)%gcd(n/gx,n/gy)!=0){
            cout<<-1<<"\n";
            continue;
        }
        int G=gcd(n/gx,n/gy);
        int k,l;
        exgcd(n/gx/G,n/gy/G,k,l);
        l=-l;
        k*=(my-mx)/G;
        int M=mx+n/gx*k;
        M=(M%n+n)%n;//M可能不在范围内，由于保证了vx与vy互质，那么周期一定是n
        int X=M*vx+x,Y=M*vy+y;
        int bx=X/n-1,by=Y/n-1,bs=(X+Y)/(2*n),bt=(max(Y-X,X-Y))/(2*n);//CF上面int128不让用abs，只能这么写qwq
        write(bx+by+bs+bt);
        cout<<"\n";
    }
    return 0;
}