【exgcd】牛客练习赛 D-青蛙兔子的约会

梦里梦外; 2024-03-22 12:49 73阅读 0赞

[D-青蛙兔子的约会\_牛客练习赛111 (nowcoder.com)][D-_111 _nowcoder.com]

题意：

![25d1bbcbb3854cff9e985788039548d1.png][]

思路：

感觉和那个青蛙的约会比较像

就是列了个方程：

a\*x+b\*y=n

考虑用exgcd解方程

然后看x在\[L,R\]有没有解

做法就是先把x的最小整数解求出来，然后考虑它的通解

x=x0+b/d\*t

暴力枚举t肯定不行，因为看数据范围是1e9，因此考虑O(1)算

一种做法是根据相对位置，将L和R都减去x，然后去看L和R之间有没有k\*p

这个比较细节

![7f7d36b9f9434dac89bff44188064506.png][]

比较这两处的l和r即可

如果l<=r就是有解，否则就是无解

Code：

#include <bits/stdc++.h>
    
    #define int long long 
    
    using namespace std;
    
    const int mxn=2e6+10; 
    const int mod=1e9+7;
    
    int a,b,n,L,R,x,y;
    
    int exgcd(int a,int b,int &x,int &y){
    	if(!b){
    		x=1,y=0;
    		return a;
    	}
    	int d=exgcd(b,a%b,y,x);
    	y-=(a/b)*x;
    	return d;
    }
    int ceil(int x,int y){
    	return (x+y-1)/y;
    }
    void solve(){
    	cin>>a>>b>>n>>L>>R;
    	int d=exgcd(a,b,x,y);
    	if(n%d!=0){
    		cout<<"NO"<<'\n';
    		return;
    	}
    	int p=b/d;
    	x=(x*n/d)%p;
    	x=(x%p+p)%p;
    	int l=L-x;
    	if(l<0) l=0;
    	else l=(L-x+p-1)/p;
    	int r=R-x;
    	if(r<0) r=-1;
    	else r=(R-x)/p;
    	if(l<=r) cout<<"YES"<<'\n';
    	else cout<<"NO"<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0; 
    }

还有一种做法就是：

如果把次数x设成从0开始，那么是不是看x在不在r-l之内就行

那就在求exgcd之前青蛙先走L次，这样次数就是从0开始了，这样就是判断次数在不在\[0,r-l\]之间

Code：

#include <bits/stdc++.h>
    
    #define int long long 
    
    using namespace std;
    
    const int mxn=2e6+10; 
    const int mod=1e9+7;
    
    int a,b,n,L,R,x,y;
    
    int exgcd(int a,int b,int &x,int &y){
    	if(!b){
    		x=1,y=0;
    		return a;
    	}
    	int d=exgcd(b,a%b,y,x);
    	y-=(a/b)*x;
    	return d;
    }
    void solve(){
    	cin>>a>>b>>n>>L>>R;
    	n-=L*a;
    	int d=exgcd(a,b,x,y);
    	if(n%d!=0){
    		cout<<"NO"<<'\n';
    		return;
    	}
    	x*=n/d;
    	y*=n/d;
    	int t=b/d;
    	int ans=(x%t+t)%t;
    	if(ans<=R-L) cout<<"YES"<<'\n';
    	else cout<<"NO"<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0; 
    }

[D-_111 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/56458/D
[25d1bbcbb3854cff9e985788039548d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/7d378cd31a3d420eb809240bb88fa4b1.png
[7f7d36b9f9434dac89bff44188064506.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/97b9e1663e2c439096013dd3649593dd.png