扩展欧几里得（五指山）

题意

思路

从起点，飞行k1个d，最后到达y：x + k1*d 同余y （在膜n的基础上）

得到： x + k1*d = y + k2 *n

其中k1，k2未知数，通过扩展欧几里得求出一组解，

要求我们求出最小正整数解：

其中：k1=k0 + k(n/gcd(n,d))

代码

#pragma comment(linker, "/STACK:1024000000,1024000000") #include <stdio.h> #include <iostream> #include <cstdlib> #include <cmath> #include <cctype> #include <string> #include <string.h> #include <cstring> #include <algorithm> #include <stack> #include <queue> #include <set> #include <map> #include <ctime> #include <vector> #include <fstream> #include <list> #include <iomanip> #include <numeric> using namespace std; typedef long long ll; typedef unsigned long long ull; #define mst(s) memset(s, 0, sizeof(s)) const int INF = 0x3f3f3f3f; #define LOCAL ll exgcd(ll a,ll b, ll &x,ll &y) { if(!b) { x=1,y=0; return a; } ll d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } int main() { int T; cin>>T; while(T--){ int n,d,x,y; cin>>n>>d>>x>>y; ll k1,k2; int _gcd=exgcd(d,n,k1,k2); // cout<<k1<<' '<<k2<<endl; if((y-x) % _gcd) cout<<"Impossible"<<endl; else{ k1 *=(y-x)/_gcd; ll _n=n/_gcd; cout<<(k1 % _n + _n)%_n<<endl; } } return 0; }