Elementary Number Theory - Extended Euclid Algorithm

Time Limit : 1 sec, Memory Limit : 65536 KB
Japanese version is here

Extended Euclid Algorithm

Given positive integers a and b, find the integer solution (x, y) to ax+by=gcd(a,b), where gcd(a,b) is the greatest common divisor of a and b.

Input

a b

Two positive integers a and b are given separated by a space in a line.

Output

Print two integers x and y separated by a space. If there are several pairs of such x and y, print that pair for which |x|+|y| is the minimal (primarily) and x ≤ y (secondarily).

Constraints

1 ≤ a, b ≤ 109

Sample Input 1

4 12

Sample Output 1

1 0

Sample Input 2

3 8

Sample Output 2

3 -1

 1 #include <bits/stdc++.h> 2  3 #define fread_siz 1024 4  5 inline int get_c(void) 6 { 7     static char buf[fread_siz]; 8     static char *head = buf + fread_siz; 9     static char *tail = buf + fread_siz;10 11     if (head == tail)12         fread(head = buf, 1, fread_siz, stdin);13 14     return *head++;15 }16 17 inline int get_i(void)18 {19     register int ret = 0;20     register int neg = false;21     register int bit = get_c();22 23     for (; bit < 48; bit = get_c())24         if (bit == ‘-‘)neg ^= true;25 26     for (; bit > 47; bit = get_c())27         ret = ret * 10 + bit - 48;28 29     return neg ? -ret : ret;30 }31 32 int exgcd(int a, int b, int &x, int &y)33 {34     if (!b)35     {36         x = 1;37         y = 0;38         return a;39     }40     int ret = exgcd(b, a%b, y, x);41     y = y - x * (a / b);42     return ret;43 }44 45 signed main(void)46 {47     int x, y;48     int a = get_i();49     int b = get_i();50     exgcd(a, b, x, y);51     printf("%d %d\n", x, y);52 }

@Author: YouSiki

扩展欧几里得 exGCD

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 扩展欧几里得 exGCD