赤裸裸的扩展GCD。。。
#include <cstdio> #include <cstring> #include <cstring> using namespace std; typedef long long LL; LL Gcd(LL a,LL b){ LL r = a % b; while(r){ a = b; b = r; r = a % b; } return b; } void Ex_Gcd(LL a,LL b,LL &x,LL &y){ if(!b){ x = 1; y = 0; return ; } Ex_Gcd(b,a % b, x,y); LL temp = x; x = y; y = temp - a / b * y; return ; } int main(){ LL a,b; while(~scanf("%I64d%I64d",&a,&b)){ LL d = Gcd(a,b); if(d != 1) printf("sorry\n"); else{ LL x,y; Ex_Gcd(a,b,x,y); LL x1 = x % b; while(x1 <= 0){ if(b < 0) x1 -=b; else x1 += b; } LL t = (x1 - x) /b; y -= a * t; printf("%I64d %I64d\n",x1,y); } } return 0; }