Rikka with Ants

81 阅读 0 评论 54 点赞

我是靠谱客的博主粗暴柜子，最近开发中收集的这篇文章主要介绍Rikka with Ants，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://www.nowcoder.com/acm/contest/148/H
来源：牛客网

题目描述

There are two small ants on Rikka's desk. If we consider Rikka's desk as a two-dimensional Cartesian coordinate system, both of them have coordinate (1,0).

Now, Rikka places three obstacles on her desk:
1. y = 0, none of the two ants can walk cross this line.
2. , only the second ant can walk cross this line.
3. , only the first ant can walk cross this line.

It's remarkable that it is allowed for the ants to stand exactly on the obstacles. For example, if a=b=c=d=1, then both of the ants can reach (1,0),(1,1),(2,1),(2,2) and none of them can reach (1,2),(2,3).

Now, the ants start to move. Their strategy is very simple: In each second, let (x,y) be the current coordinate of one ant, if it can reach (x,y+1), it will walk to this point, otherwise it will walk to (x+1,y).(Since , if the ant can reach (x,y), it can also reach (x+1,y)).

The following image shows the first ant's path when a=3,b=2:

Now, given a,b,c,d, let p1 be the first ant's path and p2 be the second ant's path. Rikka wants you to calculate the number of the points with integer coordinates which are on both p1 and p2.

输入描述:

The first line contains a single integer t(1 ≤ t ≤ 105), the number of the testcases.

For each testcase, the first line contains four integers a,b,c,d(1 ≤ a,b,c,d ≤ 109).

输出描述:

For each testcase, output a single line with a single number, the answer modulo 998244353. If p1,p2 have infinite many common points, output -1.

示例1

输入

复制

5
1 1 1 1
1 2 1 1
1 3 2 1
1 100 1 99
12 34 56 78

输出

复制

我们可以假设 $frac{a}{b}$ $>$ $frac{c}{d}$ ,如果相反，我们就交换一下。如果相等，自然就是-1.

考虑这两条线对在公共点上的点限制 :

1.考虑斜率低的直线 $frac{c}{d}$ ，那么一定有 $y<=(c/d)x$ ，因为需要在两条斜线以下么;

2.然后考虑 $y=(a/b)x$ 这条直线，因为也要在他的邻域内，所以不能离着它太远，考虑最远的情况，我们可以知道如果能往上走，但是往右走了，如果这样的话，那么现在的错误位置和应该在的位置，肯定在边长为1的正方形的对角线上，现在的关系可以表述为 $(a/b)*(x-1)>=y+1$ 。当然，这是错误最少的时候，后面可以一直往后走，也就是 $(a/b)*(x-1)>y+1$ 。所以合法的情况就是 $(a/b)*(x-1)<y+1$ 。

注：这里的（x,y)就是对答案做出贡献的（x,y)。

两条线斜率不想等，一定会有交点，求出来x就好了。然后就是求两条直线间的整点的个数，考虑y的最小值是 $(a/b)*(x-1)-1<y$ , 最大值是 $y<=(c/d)x$ ，所以对于同一个x来说他的 $y$ 的范围就可以求出来了。 $xin [1,limx]$ , 然后类欧计算的是 $[0,x]$ , 把x 换成 x+1, 然后结果就变成了 $sum_{x=0}^{limx-1} left { left lfloor frac{cx+c}{d} right rfloor -left lfloor frac{ax}{b}-1 right rfloor right }$ ，然后找个~~类欧的版子套一下，~~ 自己写一下

可能大家和我一样，考虑到可能有负数，但是我们都转换成了正数，所以直接变成了减法。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef __int128 LLL;
const LL mod=998244353;
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;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
    	LL a,b,c,d;
    	scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
    	if(a*d==b*c){
    		printf("-1n");
    		continue;
	}
	if(c*b>a*d){swap(a,c);swap(b,d);}
	LL x=d*(a+b)/(a*d-b*c);
	LL ans1=f(c,c,d,x-1),ans2=f(a,0,b,x-1);
	LL ans=((ans1+mod-ans2)%mod+x%mod+mod)%mod;
	printf("%lldn",ans);
   }
    return 0;
}