$\quad$扩展欧几里得好题。
$\quad$思路如下:
$\quad$对于形如:$ax+by=d$,这样的方程式,求整数解$(x,y)$,在学习完裴属定理和扩展欧几里得之后,我们会有如下的结论:
- 原式,任何一组解都可以通过,$ax+by=gcd(a,b)$,的普通解变换而来。
$\quad$假设$ax+by=gcd(a,b)$的普通解为$(x0,y0)$,那么任意其他解都可以写成如下形式:
- $x_{i}=x_{0} - \frac{b}{gcd(a,b)} * t , y_{i}=y_{0} + \frac{a}{gcd(a,b} * t$,其中t为任意整数
$\quad$上式,可以形象的理解成,我们在普通的解的基础上,在方程左侧,加$t$,减$t$,从而可以表示任意解。
$\quad$有了以上结论后,我们处理本题就会容易,对于$x$,的区间范围$[L,R]$,分析之后发现,假如满足$x_{0} \geq L$,我们实际最优的方案构造出特殊的$x_{i}$,使其在尽量靠近$L$,的同时使得$y_{i}$,尽可能的变大了。这样的解实际就是最优的操作策略。
$\quad$那么当$x_{0} < L$,时候,我们一样需要尽可能的靠近$L$,从而使得$y$可以尽可能的大,这样的策略是最优策略。
$\quad$通过上述分类我们就把情况讨论完毕了,至于为什么这样操作是最优策略,可以推导一下公式体会一下。
AC Code
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int a,b,n,l,r;
int exgcd(int a,int b,ll &x,ll &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;
ll x,y;
int d=exgcd(a,b,x,y);
if(n%d!=0)cout<<"NO"<<endl;
else
{
x*=n/d,y*=n/d;
if(x>=l)
{
ll res=(x-l)/(b/d);
x-=res*(b/d);
if(x>r||y+res*(a/d)<0)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}else
{
ll res=(l-x+b/d-1)/(b/d);
x+=res*(b/d);
if(x>r||y-res*(a/d)<0)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
#endif
int t;cin>>t;
while(t--)solve();
return 0;
}
请问x = n / gcd;y = n / gcd;是什么意思啊?
先把总路程中的公约数部分去掉
xi,yi那个通式+t-t啥的具体咋来的呀 o.0
就比如 a+b=c,那么a+t+b-t=c,同样的你把这个思想带入到 求解的方程就可以求出任意解
只不过需要考虑一个系数所以要写成乘法