|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<stdio.h> struct tri{ long long d,x,y; }; int gcd(int,int); struct tri exgcd(long long,long long); int main(){ long long a,b; scanf("%lld %lld",&a,&b); struct tri result = exgcd(a,b); printf("%lld %lld %lld\n",result.d,result.x,result.y); long long item = result.x * a+result.y*b; printf("%lld\n",item); return 0; } int gcd(int a,int b){ if(!b) return a; gcd(b,a%b); } struct tri exgcd(long long a,long long b){ struct tri target; if(b == 0){ target.d = a; target.x = 1; target.y = 0; return target; }else{ target = exgcd(b,a%b); long long item = target.x - (long long)(a/b)*target.y; target.x = target.y; target.y = item; return target; } } |
#详见算法导论