牛客网暑期ACM多校训练营（第十场）Rikka with Ants(类欧几里得)

本文主要是介绍牛客网暑期ACM多校训练营（第十场）Rikka with Ants(类欧几里得)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://www.nowcoder.com/acm/contest/148/H

题目大意：有两只蚂蚁从(1,0)点出发往上走，但是一只不能越过 $y=\frac{a}{b}x(a,b>0)$ ，一只不能越过 $y=\frac{c}{d}x(c,d>0)$ ，如果不能往上了就往右边一格(移动的距离一定是整数)，问这两只蚂蚁的行走路线里有多少个整点重合。

题目思路：针对一条线来说，我们可以针对蚂蚁走的点得到两个约束条件，第一个就是蚂蚁不能越过线，拿 $y=\frac{a}{b}x(a,b>0)$ 做例子，那么 $y\leq \left \lfloor \frac{a}{b}*x\right \rfloor$ ，还有一个约束条件是它现在的y+1要比它x-1的函数值要大，不然的话他在x-1就会继续往上走而不会到这里了，也就是 $y+1> \left \lfloor \frac{a}{b}*(x-1)\right \rfloor$ ，有此我们会得到两个相似的方程 $y\leqslant\left \lfloor \frac{c}{d}*x \right \rfloor$ , $y+1> \left \lfloor \frac{c}{d}*(x-1)\right \rfloor$ ,为了方便计算，我们设定 $\frac{a}{b}<\frac{c}{d}$ (不符合就交换),那么这四条方程就可缩减为两个，分别是 $y\leq \left \lfloor \frac{a}{b}*x\right \rfloor$ ， $y+1> \left \lfloor \frac{c}{d}*(x-1) \right \rfloor$ ，联立方程组就是 $\left \lfloor \frac{c}{d}*(x-1)\right \rfloor-1< y\leq \left \lfloor \frac{a}{b}*x\right \rfloor$ 。也就是我们需要求出这个范围内所有的正整点个数。所以我们需要引入一个算法叫做类欧几里得算法，类欧几里得算法能解决 $\sum_ {i=0}^n \left \lfloor \frac{a*i+c}{b}\right \rfloor$ 的问题，也可以理解成这条直线在1~n范围内有多少个整点，那么在我们这道题里面， $y\leq \left \lfloor \frac{a}{b}*x\right \rfloor$ 就被解决了，那么如何解决 $\left \lfloor \frac{c}{d}*(x-1)\right \rfloor-1< y$ 呢？我们可以换个角度来解决这个问题，可以把它转换成 $y\leq\left \lfloor \frac{c}{d}*(x-1)\right \rfloor-1$ ，由于这种约束条件需要x-1存在点，所以也就是1~n，然后就可以转换成 $\sum_{i=0}^{n-1} \left \lfloor \frac{c*i}{d}\right \rfloor$ 最后不要忘了，每个都带个-1，一共有n项，所以要加n。这里有个坑点，n的范围是10^18,a的范围是10^9，然而他需要让n*a，所以会爆long long，需要开__128

以下是代码：

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define MAXN 100005
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define LL __int128
#define mod 998244353
ll fd(ll a,ll b,ll c,ll n)
{if (a==0) return ((b/c)*(n+1))%mod;if (a>=c || b>=c) return (fd(a%c,b%c,c,n)%mod+(a/c)%mod*(n*(n+1)/2)%mod+((b/c)*(n+1))%mod)%mod;ll m=((LL)a*n+b)/c;ll v=fd(c,c-b-1,a,m-1)%mod;return ((LL)n*m-v+mod)%mod;
}
int main()
{int t;ll a,b,c,d;scanf("%d",&t);while(t--){scanf("%lld%lld%lld%lld",&a,&b,&c,&d);if(a*d==b*c)printf("-1\n");else{if(a*d>b*c){swap(a,c);swap(b,d);}ll n=(c+d)*b/(b*c-a*d);ll ans=fd(a,0,b,n);ans-=fd(c,0,d,n-1);ans+=n;ans=(ans+mod)%mod;printf("%lld\n",ans);}}
}

这篇关于牛客网暑期ACM多校训练营（第十场）Rikka with Ants(类欧几里得)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！