题目传送门 - https://www.nowcoder.com/acm/contest/148/H

题意

　　有两只蚂蚁在一个二维平面上走。一开始，他们都在点 $(1,0)$ 的位置。

　　Rikka 布置了三条规定：

　　1.　第一只蚂蚁不能走过直线 $y=cfrac{a}{b} x$ 。

　　2.　第二只蚂蚁不能走过直线 $y=cfrac{c}{d} y$ 。

　　3.　所有蚂蚁都不能走过直线 $y=0$ 。

　　每一只蚂蚁的行走方式都是一样的，即：如果能往上走，那么向上；否则向右。

　　问这两只蚂蚁走过的路径上有多少个整点是重合的，如果答案为 $infty$ ，输出 $-1$ 。

　　多组数据，$Tleq 10^5,0leq a,b,c,d leq 10^9$ 。

题解

upd(2018-08-28): 无意中发现我之前那个上界的取值写错了，40多个阅读居然没人指出QAQ……

　　首先，判掉无穷的情况：即斜率相同。

　　然后，强制 $y=cfrac ab x$ 的斜率比 $y=cfrac cd x$ 大。（即，如果小了就交换）

　　记 $f(x)=y_1=cfrac ab x,g(x)=y_2=cfrac cd x$ ，

　　因此，对于一个点 $x$ ，必然有 $y_1>y_2$ 。于是，重合的整点中，横坐标为 $x$ 的点的 $y$ 坐标必然 $leq y_2$ 。又由于 $f(x-1)>g(x-1)$ ，所以，横坐标为 $x$ 的重合的整点的 $y$ 坐标必然 $geqleftlfloor cfrac{a(x-1)}{b} ight floor$ 。

　　于是，答案就是：

$$egin{eqnarray*}&sum_{x=0}^{infty} maxleft(0,leftlfloorcfrac{c(x+1)}{d} ight floor-leftlfloorcfrac{ax-b}{b} ight floor ight)\=&sum_{x=0}^{infty} maxleft(0,leftlfloorcfrac{c(x+1)}{d} ight floor-leftlfloorcfrac{ax}{b} ight floor+1 ight)end{eqnarray*}$$

　　我们考虑取一个上界，来从公式中拿掉那个 $max$ 。

　　我们考虑到：

　　如果我们取尽量大的 $i$ ，使得

$$cfrac {ai}{b} leq cfrac{c(i+1)}{d} +1$$

　　则，对于 $x>i$，显然有：

$$leftlfloorcfrac{c(x+1)}{d} ight floor-leftlfloorcfrac{ax}{b} ight floor+1leq 0$$

　　相反，对于 $x<i$ ，有：

$$leftlfloorcfrac{c(x+1)}{d} ight floor-leftlfloorcfrac{ax}{b} ight floor+1geq 0$$

　　这两个容易证明。

　　那么我们就可以解得上界为 $i=leftlfloor cfrac{(c+d)b}{ad-bc} ight floor$ ，于是，我们可以把原式写成：

$$egin{eqnarray*}&&sum_{x=0}^{infty} maxleft(0,leftlfloorcfrac{c(x+1)}{d} ight floor-leftlfloorcfrac{ax-b}{b} ight floor ight)\&=&sum_{x=0}^{infty} maxleft(0,leftlfloorcfrac{c(x+1)}{d} ight floor-leftlfloorcfrac{ax}{b} ight floor+1 ight)\&=&sum_{x=0}^{i}left(leftlfloorcfrac{c(x+1)}{d} ight floor-leftlfloorcfrac{ax}{b} ight floor+1 ight)\&=&sum_{x=0}^{i}leftlfloorcfrac{c(x+1)}{d} ight floor-sum_{x=0}^{i}leftlfloorcfrac{ax}{b} ight floor +i+1end{eqnarray*}$$

　　上面前两个 $sum$ 是裸的类欧，直接拖一份写就可以了。

代码

#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
",calc((c+d)*b/(d*a-c*b)));
	}
	return 0;
}