链接
就是求 (m-n)*a+b*l=y-x,
类似于求解 a*x+b*y=c,r=gcd(a,b), 当 c%r==0 时有解, 用 exgcd 求出 a*x+b*y=gcd(a,b) 的解, 然后 x*c/gcd(a,b) 就是其中一个解, 最后求最小正整数解, 就是 (x%b b)%b, 要求 y 的话, 对应求解即可
- #include<map>
- #include<set>
- #include<list>
- #include<cmath>
- #include<queue>
- #include<stack>
- #include<vector>
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define se second
- #define mp make_pair
- #define pb push_back
- #define pi acos(-1.0)
- #define ll long long
- #define mod 1000000007
- #define C 0.5772156649
- #define ls l,m,rt<<1
- #define rs m+1,r,rt<<1|1
- #define pil pair<int,ll>
- #define pii pair<int,int>
- #define ull unsigned long long
- #define base 1000000000000000000
- #define fio ios::sync_with_stdio(false);cin.tie(0)
- using namespace std;
- const double g=10.0,eps=1e-12;
- const int N=100000+10,maxn=400000+10,inf=0x3f3f3f3f;
- ll gcd(ll a,ll b)
- {
- return b?gcd(b,a%b):a;
- }
- ll exgcd(ll a,ll b,ll &x,ll &y)
- {
- if(!b)
- {
- x=1,y=0;
- return a;
- }
- ll ans=exgcd(b,a%b,x,y);
- ll t=x;x=y;y=t-a/b*y;
- return ans;
- }
- int main()
- {
- ll x,y,n,m,l,a,b;
- scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
- if(m<n)swap(x,y),swap(m,n);
- ll r=gcd(m-n,l);
- if((y-x)%r!=0)return 0*puts("Impossible");
- exgcd(m-n,l,a,b);
- a*=(y-x)/r;
- a=(a%l+l)%l;
- printf("%lld\n",a);
- return 0;
- }
- /********************
- ********************/
来源: http://www.bubuko.com/infodetail-2496945.html