题目：

exgcd裸题。注意最后各种%b。注意打出正确的exgcd板子。就是别忘了/=g。

#include
     
      #include
      
       #include
       
        #define ll long longusing namespace std;ll a,b,x,y,r,A,B,C,k,g;ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;}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(){  while(1)    {      scanf("%lld%lld%lld%lld",&A,&B,&C,&k);      if(!A&&!B&&!C&&!k)return 0;      a=C;b=(1ll<