大佬的解释 题目链接 一次同余式a*x%n=b的解的存在条件是b整除gcd(a,n)。
#include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<iostream> #include<algorithm> #define LL long long using namespace std; const int maxn=4e6+10; const int inf=0x3f3f3f3f; void exgcd(LL a,LL b,LL &x,LL &y)//一次同余式的求解 { if(!b) { x=1; y=0; return ; } exgcd(b,a%b,y,x); y-=a/b*x; } int main() { LL a,b,c,d,e; while(~scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e)) { LL x=d-c,n=e,y=a-b; LL z=__gcd(x,n); if(y%z)//解存在的条件 printf("Impossible\n"); else { x/=z,y/=z,n/=z; LL p,q; exgcd(x,n,p,q);//（x*p和y同余于n） p*=y; p%=n; while(p<0) p+=n; printf("%lld\n",p);//p为最小满足的解 } } }