NEFU84——五指山（Exgcd）

传送门

 

这不是Exgcd的板子吗？

 

可以得出方程：

 

 

我们只需要套用Exgcd

 

求出最小正整数解就是了

 

#include<bits/stdc++.h> using namespace std; inline int read(){char ch=getchar();int res=0;while(!isdigit(ch))ch=getchar();while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();return res; } #define ll long long ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1,y=0;return a;}ll d=exgcd(b,a%b,x,y);ll z=x;x=y,y=z-y*(a/b);return d; } ll d,x,y,a,s,b,c,z; int main(){int T;cin>>T;while(T--){cin>>b>>a>>s>>d;int z=exgcd(a,b,x,y);x=x*(d-s)/z;if((d-s)%z) cout<<"Impossible"<<'\n';else cout<<(x%(b/z)+(b/z))%(b/z)<<'\n';}}

 

转载于:https://www.cnblogs.com/stargazer-cyk/p/10366437.html

总结

以上是生活随笔为你收集整理的NEFU84——五指山（Exgcd）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。