原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round10-H.html
有两只蚂蚁在一个二维平面上走。一开始，他们都在点 $(1,0)$ 的位置。
Rikka 布置了三条规定：
1. 第一只蚂蚁不能走过直线 $y=\cfrac{a}{b} x$ 。
2. 第二只蚂蚁不能走过直线 $y=\cfrac{c}{d} y$ 。
3. 所有蚂蚁都不能走过直线 $y=0$ 。
每一只蚂蚁的行走方式都是一样的，即：如果能往上走，那么向上；否则向右。
问这两只蚂蚁走过的路径上有多少个整点是重合的，如果答案为 $\infty$ ，输出 $-1$ 。
多组数据，$T\leq 10^5,0\leq a,b,c,d \leq 10^9$ 。
我们考虑用式子来表达一下本题的意思。
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
typedef long long LL;
typedef __int128 LLL;
LL f(LL a,LL b,LL c,LL n){
if (a==0)
return (b/c)%mod*((n+1)%mod)%mod;
if (a>=c||b>=c)
return ((LL)((LLL)a/c%mod*(n*(n+1)/2%mod))%mod
+(b/c)*(n+1)%mod+f(a%c,b%c,c,n))%mod;
LL tmp=((LLL)a*n+b)/c;
return (tmp%mod*n%mod-f(c,c-b-1,a,tmp-1)+mod)%mod;
}
LL T,a,b,c,d;
void write(LLL x){
if (x<0){
putchar(‘-‘);
x=-x;
}
if (x>9)
write(x/10);
putchar(‘0‘+x%10);
}
LL calc(LL x){
return (f(c,c,d,x)-f(a,0,b,x)+x+1+mod)%mod;
}
int main(){
scanf("%lld",&T);
while (T--){
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if (a*d==b*c){
puts("-1");
continue;
}
if (a*d<b*c)
swap(a,c),swap(b,d);
printf("%lld\n",calc((c+d)*b/(d*a-c*b)));
}
return 0;
}
2018牛客网暑假ACM多校训练赛（第十场）H Rikka with Ants 类欧几里德算法
原文：https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round10-H.html