(SWEA c++)3032. 홍준이의 숫자 놀이

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV-0U8FKZLQDFAXT&categoryId=AV-0U8FKZLQDFAXT&categoryType=CODE

SW Expert Academy

유클리드 호제법을 이용한 문제 풀이.

자세한 내용은 구글에 검색하면 설명이 잘 나와있다..!

 

#include <iostream>

using namespace std;

void extu(int r1, int r2)
{
    int r, q, s, s1 = 1, s2 = 0, t, t1 = 0, t2 = 1, tmp = r1;
    
    while(r2)
    {
        q = r1 / r2;
        r = r1 % r2;
        s = s1 - q * s2;
        t = t1 - q * t2;
        
        r1 = r2;
        r2 = r;
        s1 = s2;
        s2 = s;
        t1 = t2;
        t2 = t;
    }
    if(r1 != 1)
        cout << -1;
    else
    	cout << s1 << " " << t1;
}

int main(void)
{
    int t;
    cin >> t;
    
    for(int tc = 1; tc <= t; tc++)
    {
        int a, b;
        cin >> a >> b;
        
        cout << "#" << tc << " ";
        extu(a, b);
        cout << endl;
    }
    return 0;
}